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
AC × 3
AC × 40
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