JOI 2007 春合宿 Mall ( Prefix sum )

http://www.ioi-jp.org/camp/2007/2007-sp-tasks/2007-sp-day1_20.pdf
mall: ショッピングモール (Mall) - 2007年 日本情報オリンピック春合宿OJ | AtCoder
Get column prefix sum for each individual row, and enumerate top left corner to reduce unnecessary re-computing. No big tricks.

typedef long long ll;
typedef vector< ll > vi;
typedef vector< vi > vvi;

const int INF = 0x3f3f3f3f;

int N, M;
int A, B;
vvi G;

void solve(){
    cin >> M >> N;
    cin >> B >> A;
    G = vvi( N, vi( M ) ); // vi, vvi both take long long int
    for( int i = 0; i < N; ++i )
        for( int j = 0; j < M; ++j ){
            cin >> G[ i ][ j ];
            if( G[ i ][ j ] == -1 )
                G[ i ][ j ] = INF;
        }

    vvi row_psum( N, vi( M + 1 ) ); // 2nd dimension sets for length of prefix
    for( int i = 0; i < N; ++i )
        for( int j = 0; j < M; ++j )
            row_psum[ i ][ j + 1 ] = row_psum[ i ][ j ] + G[ i ][ j ];

    ll ans = 1e16;

    for( int i = 0; i + B - 1 < M; ++i ){
        ll sum = 0;
        for( int j = 0; j < A; ++j )
            sum += row_psum[ j ][ i + B ] - row_psum[ j ][ i ];
        ans = min( ans, sum );

        for( int j = A; j < N; ++j )
            sum -= row_psum[ j - A ][ i + B ] - row_psum[ j - A ][ i ],
            sum += row_psum[ j ][ i + B ] - row_psum[ j ][ i ],
            ans = min( ans, sum );
    }

    cout << ans << "\n";
}