ARC 025 B - チョコレート

問題

問題概要

２次元累積和。

解法

このサイトを参考にした。

paiza.hatenablog.com

白か黒をマイナスの数字として扱うことで、２次元累積和を用いて計算することができる。やり方は、まず、横方向の累積和を取り、次は、それを縦方向に累積和をとる。このように求めたmemoを利用することで、指定した長方形の中の数字の和計算量(1)で求めることができる。よって全ての長方形について調べても、計算量(h²*w²)で求めることが可能になる。

ミス

添字でバグらせた。

コード

#include <iostream>
#include <cstdio>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,f,n) for(int i=(f);i<(n);i++)
int b[110][110];
ll memo[110][110];
int main(void){
    int h, w; cin >> h >> w;
    rep(i, h)rep(j, w) cin >> b[i][j];
    rep(i, h)rep(j, w){
        if((i + j) % 2 == 0){
            b[i][j] *= -1;
        }
    }
    rep(i, h) memo[i][0] = 0;
    rep(i, w) memo[0][i] = 0;
    rep(i, h)rep(j, w){//横の累積和
        memo[i + 1][j + 1] += memo[i + 1][j] + b[i][j];
    }
    rep(i, w)rep(j, h){//2次元累積和
        memo[j + 1][i + 1] += memo[j][i + 1];
    }

    int ans = 0;
    /*
   (i, j)------------|
   |                 |
   |
   |--------------(y, x)
   */
    reps(i, 1, h + 1)reps(j, 1, w + 1){
        reps(y, i, h + 1)reps(x, j, w + 1){
            ll sum = memo[y][x];
            sum -= memo[i - 1][x];
            sum -= memo[y][j - 1];
            sum += memo[i - 1][j - 1];
            if(sum == 0){
                ans = max(ans, (y - i + 1) * (x -  j + 1));
            }
        }
    }
    printf("%d\n", ans);
    return 0;
}