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
AC × 18
AC × 20
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