Submission #2217413
Source Code Expand
#include <iostream> #include <vector> #include <algorithm> #include <cmath> using namespace std; vector<vector<int> > sum; int per(int sx, int sy, int ex, int ey) { return sum[sx][sy] + sum[ex + 1][ey + 1] - sum[sx][ey + 1] - sum[ex + 1][sy]; } // 10^5 < 257500 < 10^6 < 10^7 int main() { int N; vector<vector<int> > table; vector<int> p; vector<int> t_p; int Q; vector<int> abi; int t; // O(N * N)...2500 cin >> N; table = vector<vector<int> >(N, vector<int>(N, 0)); sum = vector<vector<int> >(N + 1, vector<int>(N + 1, 0)); p = vector<int>(N * N + 1, 0); for(int i = 0; i < N; i++) { for(int j = 0; j < N; j++) { cin >> table[i][j]; sum[i+1][j+1] = table[i][j]; } } cin >> Q; // O(Q)...2500 for(int i = 0; i < Q; i++) { cin >> t; abi.push_back(t); } // 2乗累積和の初期化 for(int i = 1; i < N + 1; i++) { for(int j = 1; j < N + 1; j++) { sum[i][j] += sum[i][j-1] + sum[i-1][j] - sum[i-1][j-1]; } } // 最大で焼ける個数がn個であるときの最大パフォーマンスを検出 // O(N * (logN + N * N * 2) // 50 * (5 + 5000) = 250000 int w; int l; int temp; int max; for(int i = 1; i <= N * N; i++) { temp = 0; max = 0; // 約数を列挙 t = sqrt(i); for(int j = 1; j <= t; j++) { if(i % j == 0) { t_p.push_back(j); t_p.push_back(i / j); } } while(t_p.size() > 0) { w = t_p.at(t_p.size() - 1); l = t_p.at(t_p.size() - 2); t_p.pop_back(); t_p.pop_back(); for(int ii = 0; ii + w - 1 < N; ii++) { for(int jj = 0; jj + l - 1 < N; jj++) { temp = per(ii, jj, ii + w - 1, jj + l - 1); if(max < temp) { max = temp; } } } t = w; w = l; l = t; for(int ii = 0; ii + w - 1 < N; ii++) { for(int jj = 0; jj + l - 1 < N; jj++) { temp = per(ii, jj, ii + w - 1, jj + l - 1); if(max < temp) { max = temp; } } } } if(max < p[i - 1]) { p[i] = p[i - 1]; } else { p[i] = max; } } // 各店員の最高パフォーマンス O(Q) 2500 for(int i = 0; i < Q; i++) { cout << p[abi[i]] << endl; } return 0; }
Submission Info
Submission Time | |
---|---|
Task | D - おいしいたこ焼きの焼き方 |
User | takusann |
Language | C++14 (GCC 5.4.1) |
Score | 100 |
Code Size | 2212 Byte |
Status | AC |
Exec Time | 14 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 | 6 ms | 256 KB |
rand1.txt | AC | 5 ms | 256 KB |
rand2.txt | AC | 8 ms | 256 KB |
rand3.txt | AC | 3 ms | 256 KB |
rand4.txt | AC | 1 ms | 256 KB |
rand_max0.txt | AC | 14 ms | 384 KB |
rand_max1.txt | AC | 14 ms | 384 KB |
rand_max2.txt | AC | 14 ms | 384 KB |
rand_max3.txt | AC | 14 ms | 256 KB |
rand_max4.txt | AC | 14 ms | 256 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 |