Submission #3068873

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

vector<ii> ranges(int W, vi& d) {
    vector<ii> r;
    int curr_from = -1;
    rep(i, W) {
        if (curr_from == -1) {
            if (d[i] == 0) {
                ;
            } else {
                curr_from = i;
            }
        } else {
            if (d[i] == 0) {
                r.pb(ii(curr_from, i));
                curr_from = -1;
            } else {
                ;
            }
        }
    }
    if (curr_from != -1) {
        r.pb(ii(curr_from, W));
    }
    return r;
}

void append_range(map<ii,int>& r_next, map<ii,int>& r_prev, vector<ii>& r){
    int L = r.size();
    rep(i, L) {
        ii k = r[i];
        r_next[k] = max(r_next[k], 1);
    }

    for (auto p : r_prev) {
        ii x = p.first;
        int ph = p.second;

        for (int i=0; i<r.size(); ++i) {
            ii y = r[i];

            if (x.second <= y.first) {
                ;
            } else if (y.second <= x.first) {
                ;
            } else {
                if (x.first <= y.first && y.second <= x.second) {
                    // y部分だけ
                    r_next[y] = max(r_next[y], ph+1);
                } else if (y.first <= x.first && y.second <= x.second) {
                    ii k(x.first, y.second);
                    r_next[k] = max(r_next[k], ph+1);
                } else if (x.first <= y.first && x.second <= y.second) {
                    ii k(y.first, x.second);
                    r_next[k] = max(r_next[k], ph+1);
                } else if (y.first <= x.first && x.second <= y.second) {
                    r_next[x] = max(r_next[x], ph+1);
                }
            }
        }
    }
}

int solve(int H, int W, vector<string>& s) {
    // fprintf(stderr, "H=%d, W=%d\n", H, W);
    vector<int> d(W);
    map<ii,int> r_prev;
    int best = max(H, W);

    for (int i=0; i<H-1; ++i) {
        // 順
        rep(c, W) {
            d[c] = (s[i][c] == s[i+1][c]);
        }
        vector<int> e(W-1, 0);
        rep(i, W-1) {
            e[i] = d[i] & d[i+1];
        }
        vector<ii> r0 = ranges(W-1, e);
        // 逆
        rep(i, W) d[i] ^= 1;
        rep(i, W-1) {
            e[i] = d[i] & d[i+1];
        }
        // vector<ii> r1 = rev_ranges(W-1, r0);
        vector<ii> r1 = ranges(W-1, e);

#ifdef DEBUG
        cerr << i << ") " << r_prev << endl;
        cerr << "  + " << r0 << endl;
        cerr << "  + " << r1 << endl;
#endif
        for (ii p : r0) {
            best = max(best, 2 * (p.second - p.first + 1));
        }
        for (ii p : r1) {
            best = max(best, 2 * (p.second - p.first + 1));
        }

        map<ii,int> r_next;
        append_range(r_next, r_prev, r0);
        append_range(r_next, r_prev, r1);
#ifdef DEBUG
        cerr << " => " << r_next << endl;
#endif

        r_prev = r_next;

        for (auto p : r_prev) {
            ii x = p.first;
            int ph = p.second;
            best = max(best, (ph+1) * (x.second - x.first + 1));
        }

    }

    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 4488 Byte
Status
Exec Time 1606 ms
Memory 6656 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 2 ms 384 KB
10.txt 775 ms 4608 KB
11.txt 84 ms 4352 KB
12.txt 153 ms 4352 KB
13.txt 155 ms 4352 KB
14.txt 156 ms 4352 KB
15.txt 158 ms 4352 KB
16.txt 159 ms 4352 KB
17.txt 159 ms 4352 KB
18.txt 1085 ms 4608 KB
19.txt 417 ms 4480 KB
2.txt 1 ms 256 KB
20.txt 497 ms 4480 KB
21.txt 482 ms 4480 KB
22.txt 472 ms 4480 KB
23.txt 516 ms 4608 KB
24.txt 172 ms 4352 KB
25.txt 154 ms 4352 KB
26.txt 1353 ms 4608 KB
27.txt 975 ms 4480 KB
28.txt 923 ms 4480 KB
29.txt 154 ms 4352 KB
3.txt 1606 ms 4480 KB
30.txt 154 ms 4352 KB
31.txt 155 ms 4352 KB
32.txt 154 ms 4352 KB
33.txt 155 ms 4352 KB
34.txt 155 ms 4352 KB
4.txt 1602 ms 4480 KB
5.txt 2 ms 384 KB
6.txt 1 ms 256 KB
7.txt 1236 ms 6656 KB
8.txt 1216 ms 4608 KB
9.txt 762 ms 4608 KB
sample1.txt 1 ms 256 KB
sample2.txt 1 ms 256 KB
sample3.txt 1 ms 256 KB