AtCoder Regular Contest 025

Submission #1676788

Source codeソースコード

// 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

Task問題 B - チョコレート
User nameユーザ名 sei0o
Created time投稿日時
Language言語 C++14 (GCC 5.4.1)
Status状態 AC
Score得点 100
Source lengthソースコード長 2904 Byte
File nameファイル名
Exec time実行時間 102 ms
Memory usageメモリ使用量 512 KB

Test case

Set

Set name Score得点 / Max score Cases
Sample - subtask0_sample-01.txt,subtask0_sample-02.txt,subtask0_sample-03.txt,subtask0_sample-04.txt,subtask0_sample-05.txt
All 100 / 100 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

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
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