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
Submission Time | |
---|---|
Task | B - チョコレート |
User | sei0o |
Language | C++14 (GCC 5.4.1) |
Score | 100 |
Code Size | 2904 Byte |
Status | AC |
Exec Time | 102 ms |
Memory | 512 KB |
Judge Result
Set Name | Sample | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 100 / 100 | ||||
Status |
|
|
Set Name | Test Cases |
---|---|
Sample | subtask0_sample-01.txt, subtask0_sample-02.txt, subtask0_sample-03.txt, subtask0_sample-04.txt, subtask0_sample-05.txt |
All | subtask0_sample-01.txt, subtask0_sample-02.txt, subtask0_sample-03.txt, subtask0_sample-04.txt, subtask0_sample-05.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_15.txt, subtask1_16.txt, subtask1_17.txt, subtask1_18.txt, subtask1_19.txt, subtask1_20.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
subtask0_sample-01.txt | AC | 1 ms | 256 KB |
subtask0_sample-02.txt | AC | 1 ms | 256 KB |
subtask0_sample-03.txt | AC | 1 ms | 256 KB |
subtask0_sample-04.txt | AC | 1 ms | 256 KB |
subtask0_sample-05.txt | AC | 1 ms | 256 KB |
subtask1_01.txt | AC | 1 ms | 256 KB |
subtask1_02.txt | AC | 1 ms | 256 KB |
subtask1_03.txt | AC | 1 ms | 256 KB |
subtask1_04.txt | AC | 1 ms | 256 KB |
subtask1_05.txt | AC | 2 ms | 256 KB |
subtask1_06.txt | AC | 2 ms | 256 KB |
subtask1_07.txt | AC | 1 ms | 256 KB |
subtask1_08.txt | AC | 2 ms | 256 KB |
subtask1_09.txt | AC | 101 ms | 384 KB |
subtask1_10.txt | AC | 15 ms | 256 KB |
subtask1_11.txt | AC | 83 ms | 384 KB |
subtask1_12.txt | AC | 83 ms | 384 KB |
subtask1_13.txt | AC | 83 ms | 384 KB |
subtask1_14.txt | AC | 99 ms | 384 KB |
subtask1_15.txt | AC | 102 ms | 384 KB |
subtask1_16.txt | AC | 81 ms | 384 KB |
subtask1_17.txt | AC | 80 ms | 384 KB |
subtask1_18.txt | AC | 1 ms | 256 KB |
subtask1_19.txt | AC | 1 ms | 256 KB |
subtask1_20.txt | AC | 97 ms | 512 KB |