Submission #1025052
Source Code Expand
#include <bits/stdc++.h>
#define REP(i,n) for(int i=0; i<(int)(n); ++i)
#define FOR(i,k,n) for(int i=(k);i<(int)(n);++i)
typedef long long int ll;
using namespace std;
int D[55][55];
int acc[55][55];
int P[2501];
int memo[2501];
int area(int x, int y, int w, int h) {
return acc[x+w][y+h] - acc[x+w][y] - acc[x][y+h] + acc[x][y];
}
int main(void) {
int N, Q;
cin >> N;
REP(i, N) REP(j, N) cin >> D[i][j];
cin >> Q;
REP(i, Q) cin >> P[i];
REP(j, N+1) acc[0][j] = 0;
FOR(i, 1, N+1) {
int row = 0;
acc[i][0] = 0;
FOR(j, 1, N+1) {
row += D[i-1][j-1];
acc[i][j] = acc[i-1][j] + row;
}
}
REP(i, 2501) memo[i] = 0;
REP(w, N+1) {
REP(h, N+1) {
REP(x, N-w+1) {
REP(y, N-h+1) {
memo[w*h] = max(memo[w*h], area(x, y, w, h));
}
}
}
}
FOR(i, 1, 2501) memo[i] = max(memo[i], memo[i-1]);
REP(i, Q) cout << memo[P[i]] << endl;
}
Submission Info
Submission Time |
|
Task |
D - おいしいたこ焼きの焼き方 |
User |
kivantium |
Language |
C++ (G++ 4.6.4) |
Score |
100 |
Code Size |
1068 Byte |
Status |
AC |
Exec Time |
29 ms |
Memory |
1048 KB |
Judge Result
Set Name |
Subtask1 |
Subtask2 |
Score / Max Score |
50 / 50 |
50 / 50 |
Status |
|
|
Set Name |
Test Cases |
Subtask1 |
sub0.txt, sub1.txt, sub2.txt, sub_rand_max0.txt, sub_rand_max1.txt, sub_rand_max2.txt, sub_rand_max3.txt, sub_rand_min0.txt, s1.txt, s2.txt, sub0.txt, sub1.txt, sub2.txt, sub_rand_max0.txt, sub_rand_max1.txt, sub_rand_max2.txt, sub_rand_max3.txt, sub_rand_min0.txt |
Subtask2 |
rand0.txt, rand1.txt, rand2.txt, rand3.txt, rand4.txt, rand_max0.txt, rand_max1.txt, rand_max2.txt, rand_max3.txt, rand_max4.txt, s1.txt, s2.txt, sub0.txt, sub1.txt, sub2.txt, sub_rand_max0.txt, sub_rand_max1.txt, sub_rand_max2.txt, sub_rand_max3.txt, sub_rand_min0.txt |
Case Name |
Status |
Exec Time |
Memory |
rand0.txt |
AC |
22 ms |
1048 KB |
rand1.txt |
AC |
20 ms |
1044 KB |
rand2.txt |
AC |
25 ms |
920 KB |
rand3.txt |
AC |
19 ms |
920 KB |
rand4.txt |
AC |
18 ms |
920 KB |
rand_max0.txt |
AC |
27 ms |
1048 KB |
rand_max1.txt |
AC |
29 ms |
920 KB |
rand_max2.txt |
AC |
28 ms |
920 KB |
rand_max3.txt |
AC |
29 ms |
1044 KB |
rand_max4.txt |
AC |
28 ms |
912 KB |
s1.txt |
AC |
17 ms |
916 KB |
s2.txt |
AC |
18 ms |
920 KB |
sub0.txt |
AC |
17 ms |
916 KB |
sub1.txt |
AC |
17 ms |
1044 KB |
sub2.txt |
AC |
19 ms |
920 KB |
sub_rand_max0.txt |
AC |
19 ms |
1044 KB |
sub_rand_max1.txt |
AC |
17 ms |
920 KB |
sub_rand_max2.txt |
AC |
19 ms |
916 KB |
sub_rand_max3.txt |
AC |
19 ms |
1048 KB |
sub_rand_min0.txt |
AC |
19 ms |
912 KB |