Grass Cutting

2 secs 1024 MB

二次元における四角形の範囲の和を求めるには、二次元累積和を用いることが有効です。
二次元累積和を用いることにより、累積和の前計算で $O(N^2)$ の計算量がかかりますが、 $A \times B$ の範囲の和を $O(1)$ で求めることができます。
よって、十分高速にこの問題を解くことができました。

実装例(C++)

#include<bits/stdc++.h>

using namespace std;

int main(){
    int n, a, b;
    cin >> n >> a >> b;
    
    vector<vector<long long>> v(n, vector<long long>(n));
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            cin >> v[i][j];
        }
    }
    
    vector<vector<long long>> sum(n + 1, vector<long long>(n + 1));
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            sum[i+1][j+1] += sum[i+1][j] + sum[i][j+1] - sum[i][j] + v[i][j];
        }
    }
    long long ans = 0;
    for(int i = 0; i < n - a + 1; i++){
        for(int j = 0; j < n - b + 1; j++){
            ans = max(ans, sum[i + a][j + b] - sum[i + a][j] - sum[i][j + b] + sum[i][j]);
        }
    }
    cout << ans << endl;
}