Submission #1676788

---

Source Code Expand

// 2d cumsum

#include <iostream>
#include <queue>
#include <vector>
#include <cmath>
#include <algorithm>
#include <map>
#include <numeric>

using namespace std;
using ll = long long;
const ll INF = 1e9;
const ll MOD = 1e9 + 7;

int main() {
    int H, W;
    cin >> H >> W;
    int w[H][W], b[H][W];
    int wsum[H][W], bsum[H][W];
    for (int i = 0; i < H; i++) {
        for (int k = 0; k < W; k++) {
            wsum[i][k] = 0;
            bsum[i][k] = 0;
        }
    }

    for (int i = 0; i < H; i++) {
        for (int k = 0; k < W; k++) {
            int c;
            cin >> c;
            bool whi = (i % 2 != k % 2);
            if (whi) {
                w[i][k] = c;
                if (k < 1) {
                    wsum[i][k] = w[i][k];
                } else {
                    wsum[i][k] = w[i][k] + wsum[i][k-1];
                }

                bsum[i][k] = bsum[i][max(k-1, 0)];
            } else {
                b[i][k] = c;
                if (k < 1) {
                    bsum[i][k] = b[i][k];
                } else {
                    bsum[i][k] = b[i][k] + bsum[i][k-1];
                }

                wsum[i][k] = wsum[i][max(k-1, 0)];
            }
        }
    }

    for (int i = 1; i < H; i++) {
        for (int k = 0; k < W; k++) {
            wsum[i][k] = wsum[i][k] + wsum[i-1][k];
            bsum[i][k] = bsum[i][k] + bsum[i-1][k];
        }
    }

//    for (int i = 0; i < H; i++) {
//        for (int k = 0; k < W; k++) {
//            cout << bsum[i][k] << " ";
//        }
//        cout << endl;
//    }
//    cout << endl;
//    for (int i = 0; i < H; i++) {
//        for (int k = 0; k < W; k++) {
//            cout << wsum[i][k] << " ";
//        }
//        cout << endl;
//    }

    int mx = 0;
    for (int le = 0; le < W; le++) {
        for (int ri = le; ri < W; ri++) {
            for (int to = 0; to < H; to++) {
                for (int bo = to; bo < H; bo++) {
//                    cout << le << " " << ri << " " << to << " " << bo << " " << mx << endl;
                    int ba = bsum[bo][ri];
                    int wa = wsum[bo][ri];

                    if (to > 0) {
                        ba -= bsum[to-1][ri];
                        wa -= wsum[to-1][ri];
                    }
                    if (le > 0) {
                        ba -= bsum[bo][le-1];
                        wa -= wsum[bo][le-1];
                    }
                    if (to > 0 && le > 0) {
                        ba += bsum[to-1][le-1];
                        wa += wsum[to-1][le-1];
                    }


                    if (ba == wa) {
                        mx = max(mx, (bo - to + 1) * (ri - le + 1));
                    }
                }
            }
        }
    }

    cout << mx << endl;

    return 0;
}

Submission Info

Judge Result