Submission #2214386
Source Code Expand
#include <algorithm> #include <iostream> #include <map> #include <vector> #define REP(i, n) for (int i = 0; i < n; i++) #define FOR(i, m, n) for (int i = m; i < n; i++) #define ALL(a) (a).begin(), (a).end() #define INF 10000000 #define MOD 1000000007 using namespace std; int main(void) { int N; cin >> N; vector<vector<int>> d(N, vector<int>(N)); vector<vector<int>> sum(N, vector<int>(N)); REP(i, N) REP(j, N) cin >> d[i][j]; // 2D 累積和 for (int y = 0; y < N; y++) { for (int x = 0; x < N; x++) { if (x == 0) sum[x][y] = d[x][y]; else sum[x][y] = sum[x - 1][y] + d[x][y]; } if (y != 0) { for (int x = 0; x < N; x++) { sum[x][y] += sum[x][y - 1]; } } } map<int, int> result; for (int x_start = 0; x_start < N; x_start++) { for (int y_start = 0; y_start < N; y_start++) { for (int x_end = x_start; x_end < N; x_end++) { for (int y_end = y_start; y_end < N; y_end++) { int all = sum[x_end][y_end]; if (y_start >= 1) all -= sum[x_end][y_start - 1]; if (x_start >= 1) all -= sum[x_start - 1][y_end]; if (y_start >= 1 && x_start >= 1) all += sum[x_start - 1][y_start - 1]; int area = (x_end - x_start + 1) * (y_end - y_start + 1); if (result.find(area) != result.end()) result[area] = std::max(all, result[area]); else result[area] = all; } } } } int current_max = -1; for (int area = 1; area <= N * N; area++) { if (result.find(area) != result.end()) { current_max = std::max(result[area], current_max); result[area] = current_max; } else result[area] = current_max; } int Q; cin >> Q; REP(i, Q) { int area; cin >> area; cout << result[area] << endl; } return 0; }
Submission Info
Submission Time | |
---|---|
Task | D - おいしいたこ焼きの焼き方 |
User | y1r |
Language | C++14 (GCC 5.4.1) |
Score | 100 |
Code Size | 2210 Byte |
Status | AC |
Exec Time | 195 ms |
Memory | 384 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 | 95 ms | 384 KB |
rand1.txt | AC | 48 ms | 384 KB |
rand2.txt | AC | 87 ms | 384 KB |
rand3.txt | AC | 12 ms | 256 KB |
rand4.txt | AC | 1 ms | 256 KB |
rand_max0.txt | AC | 194 ms | 384 KB |
rand_max1.txt | AC | 194 ms | 384 KB |
rand_max2.txt | AC | 194 ms | 384 KB |
rand_max3.txt | AC | 195 ms | 384 KB |
rand_max4.txt | AC | 194 ms | 384 KB |
s1.txt | AC | 1 ms | 256 KB |
s2.txt | AC | 1 ms | 256 KB |
sub0.txt | AC | 1 ms | 256 KB |
sub1.txt | AC | 1 ms | 256 KB |
sub2.txt | AC | 1 ms | 256 KB |
sub_rand_max0.txt | AC | 1 ms | 256 KB |
sub_rand_max1.txt | AC | 1 ms | 256 KB |
sub_rand_max2.txt | AC | 1 ms | 256 KB |
sub_rand_max3.txt | AC | 1 ms | 256 KB |
sub_rand_min0.txt | AC | 1 ms | 256 KB |