BONUS - VOI 2011 Phần thưởng
Tác giả: happyboy99x
Ngôn ngữ: C++
#include <cstdio>
#define MAX 1000+5
int f[MAX][MAX], a[MAX][MAX];
int n, k;
int max( int a, int b ) {
return a > b ? a : b;
}
int main() {
scanf( "%d%d", &n, &k );
for( int i = 0; i < n; ++i )
for( int j = 0; j < n; ++j ) scanf( "%d", &a[i][j] );
for( int i = 0; i <= n; ++i )
for( int j = 0; j <= n; ++j )
f[i][j] = (i||j) ? a[i-1][j-1] + f[i-1][j] + f[i][j-1] - f[i-1][j-1] : 0;
int res = 0;
for( int i = k; i <= n; ++i )
for( int j = k; j <= n; ++j )
res = max(res, f[i][j] - f[i-k][j] - f[i][j-k] + f[i-k][j-k]);
printf( "%d\n", res );
return 0;
}