Submission #3070655

Source Code Expand

Copy
#include <bits/stdc++.h>
using namespace std;

#define NDEBUG
#ifdef DEBUG
#include "../cout11.h"
#undef NDEBUG
#endif
#include <cassert>

typedef long long ll;
typedef long double Double;
typedef unsigned long long ull;
typedef pair<int,int> ii;
typedef pair<ll,ll> llll;
typedef pair<double,double> dd;

typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<ii> vii;
typedef vector<vector<ii>> vvii;
typedef vector<ll> vll;
typedef vector<string> vs;
typedef vector<double> vd;
typedef vector<long double> vD;

#define sz(a)  int((a).size())
#define pb  push_back
#define FOR(var,from,to) for(int var=(from);var<=(to);++var)
#define rep(var,n)  for(int var=0;var<(n);++var)
#define rep1(var,n)  for(int var=1;var<=(n);++var)
#define repC2(vari,varj,n)  for(int vari=0;vari<(n)-1;++vari)for(int varj=vari+1;varj<(n);++varj)
#define ALL(c)  (c).begin(),(c).end()
#define RALL(c)  (c).rbegin(),(c).rend()
#define tr(i,c)  for(auto i=(c).begin(); i!=(c).end(); ++i)
#define found(s,e)  ((s).find(e)!=(s).end())
#define mset(arr,val)  memset(arr,val,sizeof(arr))
#define mid(x,y) ((x)+((y)-(x))/2)
#define IN(x,a,b) ((a)<=(x)&&(x)<=(b))
#define cons make_pair


long long max_box_area_in_histogram(vector<int>& a) {
    int N = a.size();

    vector<int> L(N);
    stack<int> st;

    for (int i=0; i<N; ++i) {
        while (!st.empty() && a[st.top()] >= a[i]) {
            st.pop();
        }
        L[i] = (st.empty() ? -1 : st.top())+1;
        st.push(i);
    }

    while (!st.empty()) st.pop();

    vector<int> R(N);
    for (int i=N-1; i>=0; --i) {
        while (!st.empty() && a[st.top()] >= a[i]) {
            st.pop();
        }
        R[i] = (st.empty() ? N : st.top())-1;
        st.push(i);
    }

    long long smax = 0;
    for (int i=0; i<N; ++i) {
        int h = a[i], w = R[i] - L[i] + 1;
        // ll s = (long long)h * w;
        ll s = (long long)(h + 1)*(w + 1);
        smax = max(smax, s);
    }

    return smax;
}

ll solve(int H, int W, vector<string>& s) {
    vvi a(H-1, vi(W-1, 0));
    rep(r, H-1) {
        rep(c, W-1) {
            a[r][c] = (s[r][c] == '#') ^ (s[r][c+1] == '#')
                    ^ (s[r+1][c] == '#') ^ (s[r+1][c+1] == '#');
        }
    }

    ll best = max(W, H);

    vi histo(W-1, 0);
    rep(r, H-1){
        rep(c, W-1) {
            if (a[r][c]) histo[c] = 0;
            else         histo[c]++;
        }
        best = max(best, max_box_area_in_histogram(histo));
    }

    return best;
}

int main() {
    int H, W; cin >> H >> W;
    vector<string> s(H);
    rep(i, H) cin >> s[i];
    cout << solve(H,W,s) << endl;
    return 0;
}

Submission Info

Submission Time
Task F - Flip and Rectangles
User naoya_t
Language C++14 (GCC 5.4.1)
Score 700
Code Size 2731 Byte
Status
Exec Time 252 ms
Memory 20096 KB

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 sample1.txt, sample2.txt, sample3.txt
All 700 / 700 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 3 ms 512 KB
10.txt 234 ms 20096 KB
11.txt 104 ms 12544 KB
12.txt 192 ms 19968 KB
13.txt 195 ms 20096 KB
14.txt 197 ms 19968 KB
15.txt 198 ms 20096 KB
16.txt 198 ms 20096 KB
17.txt 197 ms 20096 KB
18.txt 243 ms 19968 KB
19.txt 206 ms 20096 KB
2.txt 1 ms 256 KB
20.txt 211 ms 19968 KB
21.txt 211 ms 20096 KB
22.txt 211 ms 20096 KB
23.txt 214 ms 20096 KB
24.txt 190 ms 20096 KB
25.txt 190 ms 20096 KB
26.txt 248 ms 20096 KB
27.txt 231 ms 20096 KB
28.txt 229 ms 20096 KB
29.txt 192 ms 20096 KB
3.txt 252 ms 20096 KB
30.txt 197 ms 20096 KB
31.txt 197 ms 20096 KB
32.txt 200 ms 20096 KB
33.txt 200 ms 20096 KB
34.txt 200 ms 20096 KB
4.txt 252 ms 20096 KB
5.txt 3 ms 512 KB
6.txt 1 ms 256 KB
7.txt 252 ms 20096 KB
8.txt 251 ms 20096 KB
9.txt 233 ms 20096 KB
sample1.txt 1 ms 256 KB
sample2.txt 1 ms 256 KB
sample3.txt 1 ms 256 KB