Submission #1966260
Source Code Expand
import java.io.*; import java.util.*; import java.math.*; // import java.awt.Point; public class Main { InputStream is; PrintWriter out; String INPUT = ""; long MOD = 1_000_000_007; int inf = Integer.MAX_VALUE/2; void solve(){ int x = ni(); int y = ni(); char[][] map = nm(x,y); int[] dx = {0,0,1,1}; int[] dy = {0,1,0,1}; int[][] nmap = new int[x-1][y-1]; for(int i = 0; i < x-1; i++){ for(int j = 0; j < y-1; j++){ int a = 0; for(int k = 0; k < 4; k++){ int cx = i + dx[k]; int cy = j + dy[k]; if(map[cx][cy]=='.') a++; } if(a%2==0) nmap[i][j] = 1; else nmap[i][j] = 0; } } long ans = maxRect(nmap[0]); for(int i = 1; i < x-1; i++){ for(int j = 0; j < y-1; j++){ if(nmap[i][j]==1) nmap[i][j] += nmap[i-1][j]; } ans = Math.max(ans, maxRect(nmap[i])); } ans = Math.max(x,ans); ans = Math.max(y,ans); out.println(ans); } public static long maxRect(int[] a) { int n = a.length; int[] stack = new int[n]; int[] left = new int[n]; int p = 0; long max = 0; for(int i = 0;i < n;i++){ int o = p; while(p > 0 && stack[p-1] >= a[i]){ p--; max = Math.max(max, (long)(i-1-left[p]+1+1)*(stack[p]+1)); } if(o == p)left[p] = i; stack[p++] = a[i]; } while(p > 0){ p--; max = Math.max(max, (long)(n-1-left[p]+1+1)*(stack[p]+1)); } return max; } void run() throws Exception { is = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes()); out = new PrintWriter(System.out); long s = System.currentTimeMillis(); solve(); out.flush(); if(!INPUT.isEmpty())tr(System.currentTimeMillis()-s+"ms"); } public static void main(String[] args) throws Exception { new Main().run(); } private byte[] inbuf = new byte[1024]; private int lenbuf = 0, ptrbuf = 0; private int readByte() { if(lenbuf == -1)throw new InputMismatchException(); if(ptrbuf >= lenbuf){ ptrbuf = 0; try { lenbuf = is.read(inbuf); } catch (IOException e) { throw new InputMismatchException(); } if(lenbuf <= 0)return -1; } return inbuf[ptrbuf++]; } private boolean isSpaceChar(int c) { return !(c >= 33 && c <= 126); } private int skip() { int b; while((b = readByte()) != -1 && isSpaceChar(b)); return b; } private double nd() { return Double.parseDouble(ns()); } private char nc() { return (char)skip(); } private String ns() { int b = skip(); StringBuilder sb = new StringBuilder(); while(!(isSpaceChar(b) && b != ' ')){ sb.appendCodePoint(b); b = readByte(); } return sb.toString(); } private char[] ns(int n) { char[] buf = new char[n]; int b = skip(), p = 0; while(p < n && !(isSpaceChar(b))){ buf[p++] = (char)b; b = readByte(); } return n == p ? buf : Arrays.copyOf(buf, p); } private char[][] nm(int n, int m) { char[][] map = new char[n][]; for(int i = 0;i < n;i++)map[i] = ns(m); return map; } private int[] na(int n) { int[] a = new int[n]; for(int i = 0;i < n;i++)a[i] = ni(); return a; } private int ni() { int num = 0, b; boolean minus = false; while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-')); if(b == '-'){ minus = true; b = readByte(); } while(true){ if(b >= '0' && b <= '9'){ num = num * 10 + (b - '0'); }else{ return minus ? -num : num; } b = readByte(); } } private long nl() { long num = 0; int b; boolean minus = false; while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-')); if(b == '-'){ minus = true; b = readByte(); } while(true){ if(b >= '0' && b <= '9'){ num = num * 10 + (b - '0'); }else{ return minus ? -num : num; } b = readByte(); } } private static void tr(Object... o) { System.out.println(Arrays.deepToString(o)); } }
Submission Info
Submission Time | |
---|---|
Task | F - Flip and Rectangles |
User | yuya178 |
Language | Java8 (OpenJDK 1.8.0) |
Score | 700 |
Code Size | 5027 Byte |
Status | AC |
Exec Time | 305 ms |
Memory | 72532 KB |
Judge Result
Set Name | Sample | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 700 / 700 | ||||
Status |
|
|
Set Name | Test Cases |
---|---|
Sample | sample1.txt, sample2.txt, sample3.txt |
All | sample1.txt, sample2.txt, sample3.txt, 1.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 2.txt, 20.txt, 21.txt, 22.txt, 23.txt, 24.txt, 25.txt, 26.txt, 27.txt, 28.txt, 29.txt, 3.txt, 30.txt, 31.txt, 32.txt, 33.txt, 34.txt, 4.txt, 5.txt, 6.txt, 7.txt, 8.txt, 9.txt, sample1.txt, sample2.txt, sample3.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
1.txt | AC | 72 ms | 19284 KB |
10.txt | AC | 263 ms | 68820 KB |
11.txt | AC | 224 ms | 47060 KB |
12.txt | AC | 271 ms | 68820 KB |
13.txt | AC | 286 ms | 70612 KB |
14.txt | AC | 299 ms | 68436 KB |
15.txt | AC | 274 ms | 67384 KB |
16.txt | AC | 255 ms | 68564 KB |
17.txt | AC | 243 ms | 68436 KB |
18.txt | AC | 278 ms | 68564 KB |
19.txt | AC | 256 ms | 68564 KB |
2.txt | AC | 70 ms | 21076 KB |
20.txt | AC | 258 ms | 70100 KB |
21.txt | AC | 259 ms | 70356 KB |
22.txt | AC | 255 ms | 67156 KB |
23.txt | AC | 260 ms | 70484 KB |
24.txt | AC | 234 ms | 67028 KB |
25.txt | AC | 244 ms | 67924 KB |
26.txt | AC | 267 ms | 70484 KB |
27.txt | AC | 260 ms | 68308 KB |
28.txt | AC | 269 ms | 70484 KB |
29.txt | AC | 295 ms | 71124 KB |
3.txt | AC | 305 ms | 67796 KB |
30.txt | AC | 279 ms | 67540 KB |
31.txt | AC | 255 ms | 70484 KB |
32.txt | AC | 253 ms | 67540 KB |
33.txt | AC | 259 ms | 72532 KB |
34.txt | AC | 256 ms | 67540 KB |
4.txt | AC | 296 ms | 70356 KB |
5.txt | AC | 74 ms | 19280 KB |
6.txt | AC | 69 ms | 20692 KB |
7.txt | AC | 253 ms | 70484 KB |
8.txt | AC | 275 ms | 67412 KB |
9.txt | AC | 262 ms | 66772 KB |
sample1.txt | AC | 68 ms | 19284 KB |
sample2.txt | AC | 68 ms | 20180 KB |
sample3.txt | AC | 67 ms | 19284 KB |