Submission #1966257
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])); } 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 | 0 |
Code Size | 4963 Byte |
Status | WA |
Exec Time | 296 ms |
Memory | 70836 KB |
Judge Result
Set Name | Sample | All | ||||||
---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 0 / 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 | WA | 74 ms | 18388 KB |
10.txt | AC | 244 ms | 68532 KB |
11.txt | AC | 234 ms | 45488 KB |
12.txt | AC | 275 ms | 68560 KB |
13.txt | AC | 292 ms | 70836 KB |
14.txt | AC | 255 ms | 68560 KB |
15.txt | AC | 263 ms | 69972 KB |
16.txt | AC | 247 ms | 67484 KB |
17.txt | AC | 242 ms | 67668 KB |
18.txt | AC | 257 ms | 70484 KB |
19.txt | AC | 256 ms | 68692 KB |
2.txt | AC | 70 ms | 18004 KB |
20.txt | AC | 255 ms | 68052 KB |
21.txt | AC | 257 ms | 68560 KB |
22.txt | AC | 249 ms | 68564 KB |
23.txt | AC | 255 ms | 70228 KB |
24.txt | AC | 247 ms | 70480 KB |
25.txt | AC | 242 ms | 68436 KB |
26.txt | AC | 266 ms | 68432 KB |
27.txt | AC | 267 ms | 70100 KB |
28.txt | AC | 267 ms | 70484 KB |
29.txt | AC | 280 ms | 70480 KB |
3.txt | WA | 296 ms | 68688 KB |
30.txt | AC | 282 ms | 68820 KB |
31.txt | AC | 228 ms | 68308 KB |
32.txt | AC | 244 ms | 68436 KB |
33.txt | AC | 251 ms | 65108 KB |
34.txt | AC | 254 ms | 70612 KB |
4.txt | AC | 296 ms | 67024 KB |
5.txt | AC | 71 ms | 19540 KB |
6.txt | AC | 70 ms | 18772 KB |
7.txt | AC | 280 ms | 70228 KB |
8.txt | AC | 290 ms | 69256 KB |
9.txt | AC | 256 ms | 68308 KB |
sample1.txt | AC | 69 ms | 17876 KB |
sample2.txt | AC | 69 ms | 21076 KB |
sample3.txt | AC | 69 ms | 19156 KB |