Submission #2203856
Source Code Expand
#include <iostream>
#include <algorithm>
#include <cmath>
#define rep(i, a, n) for(int i = a;i < n;i++)
#define repe(i, a, n) for(int i = a;i <= n;i++)
#define repr(i, a, n) for(int i = a;i > n;i--)
#define INF 999999999
using namespace std;
int n;
int d[60][60];
int q;
int p[2510];
int ans[2510];
void makeAcc(){
rep(i, 0, n)
rep(j, 1, n) d[i][j] += d[i][j-1];
rep(i, 1, n)
rep(j, 0, n) d[i][j] += d[i-1][j];
}
int acc(int i1, int j1, int i2, int j2){
if(i1-1 < 0 && j1-1 < 0) return d[i2][j2];
if(i1-1 < 0) return d[i2][j2] - d[i2][j1-1];
if(j1-1 < 0) return d[i2][j2] - d[i1-1][j2];
return d[i2][j2] - d[i2][j1-1] - d[i1-1][j2] + d[i1-1][j1-1];
}
void makeAns(){
rep(i1, 0, n)
rep(j1, 0, n)
rep(i2, i1, n)
rep(j2, j1, n)
ans[(i2-i1+1)*(j2-j1+1)] = max(ans[(i2-i1+1)*(j2-j1+1)], acc(i1, j1, i2, j2));
int maxD = ans[1];
repe(i, 2, n*n){
maxD = max(maxD, ans[i]);
if(ans[i] && ans[i] < maxD) ans[i] = maxD;
}
}
void solve(){
rep(i, 0, q)
cout << ans[p[i]] << endl;
}
int main(){
cin >> n;
rep(i, 0, n)
rep(j, 0, n) cin >> d[i][j];
cin >> q;
rep(i, 0, q) cin >> p[i];
makeAcc();
makeAns();
solve();
return 0;
}
Submission Info
Submission Time |
|
Task |
D - おいしいたこ焼きの焼き方 |
User |
AqFv |
Language |
C++14 (GCC 5.4.1) |
Score |
0 |
Code Size |
1239 Byte |
Status |
WA |
Exec Time |
13 ms |
Memory |
256 KB |
Judge Result
Set Name |
Subtask1 |
Subtask2 |
Score / Max Score |
0 / 50 |
0 / 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 |
WA |
6 ms |
256 KB |
rand1.txt |
WA |
5 ms |
256 KB |
rand2.txt |
WA |
8 ms |
256 KB |
rand3.txt |
WA |
2 ms |
256 KB |
rand4.txt |
WA |
1 ms |
256 KB |
rand_max0.txt |
WA |
13 ms |
256 KB |
rand_max1.txt |
WA |
13 ms |
256 KB |
rand_max2.txt |
WA |
13 ms |
256 KB |
rand_max3.txt |
WA |
13 ms |
256 KB |
rand_max4.txt |
WA |
13 ms |
256 KB |
s1.txt |
AC |
1 ms |
256 KB |
s2.txt |
AC |
1 ms |
256 KB |
sub0.txt |
WA |
1 ms |
256 KB |
sub1.txt |
WA |
1 ms |
256 KB |
sub2.txt |
WA |
1 ms |
256 KB |
sub_rand_max0.txt |
WA |
1 ms |
256 KB |
sub_rand_max1.txt |
WA |
1 ms |
256 KB |
sub_rand_max2.txt |
WA |
1 ms |
256 KB |
sub_rand_max3.txt |
WA |
1 ms |
256 KB |
sub_rand_min0.txt |
AC |
1 ms |
256 KB |