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
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 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