結果

問題 No.655 E869120 and Good Triangles
ユーザー e869120e869120
提出日時 2018-01-28 13:25:57
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 1,599 ms / 2,500 ms
コード長 1,937 bytes
コンパイル時間 800 ms
コンパイル使用メモリ 77,500 KB
実行使用メモリ 363,776 KB
最終ジャッジ日時 2024-10-10 02:21:07
合計ジャッジ時間 30,360 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,248 KB
testcase_02 AC 2 ms
5,248 KB
testcase_03 AC 2 ms
5,248 KB
testcase_04 AC 2 ms
5,248 KB
testcase_05 AC 2 ms
5,248 KB
testcase_06 AC 2 ms
5,248 KB
testcase_07 AC 2 ms
5,248 KB
testcase_08 AC 2 ms
5,248 KB
testcase_09 AC 2 ms
5,248 KB
testcase_10 AC 1,529 ms
362,988 KB
testcase_11 AC 1,564 ms
363,776 KB
testcase_12 AC 1,561 ms
363,168 KB
testcase_13 AC 1,531 ms
363,648 KB
testcase_14 AC 1,551 ms
363,520 KB
testcase_15 AC 1,541 ms
363,120 KB
testcase_16 AC 1,569 ms
363,648 KB
testcase_17 AC 1,578 ms
363,648 KB
testcase_18 AC 1,565 ms
363,648 KB
testcase_19 AC 1,540 ms
363,776 KB
testcase_20 AC 1,560 ms
363,648 KB
testcase_21 AC 1,599 ms
363,648 KB
testcase_22 AC 1,547 ms
363,520 KB
testcase_23 AC 1,521 ms
363,520 KB
testcase_24 AC 1,153 ms
361,600 KB
testcase_25 AC 1,110 ms
361,600 KB
testcase_26 AC 1,088 ms
361,600 KB
testcase_27 AC 1,147 ms
361,600 KB
testcase_28 AC 1,081 ms
361,472 KB
testcase_29 AC 1,124 ms
361,600 KB
testcase_30 AC 2 ms
5,248 KB
testcase_31 AC 2 ms
5,248 KB
testcase_32 AC 3 ms
5,248 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

long long n, k, r, a[4009][4009], b[4009][4009], c[4009][4009], dp[4009][4009]; queue<pair<int, int>>Q;

long long sum(long long p, long long q, long long r) {
	long long res = c[p][q] - c[p + r][q + r] - (b[p + r][q + r - 1] - b[p + r][q - 1]);
	return res;
}

int main() {
	cin >> n >> k >> r;
	for (int i = 1; i <= n; i++) { for (int j = 1; j <= i; j++)a[i][j] = (1 << 30); }
	for (int i = 1; i <= k; i++) {
		int x, y; cin >> x >> y;
		a[x][y] = 0; Q.push(make_pair(x, y));
	}
	while (!Q.empty()) {
		pair<int, int>a1 = Q.front(); Q.pop();
		int dx[6] = { -1,-1,0,0,1,1 }, dy[6] = { -1,0,-1,1,0,1 };
		for (int i = 0; i < 6; i++) {
			int cx = a1.first + dx[i], cy = a1.second + dy[i];
			if (cy <= 0 || cx > n || cx < cy) continue;
			if (a[cx][cy] > a[a1.first][a1.second] + 1) {
				a[cx][cy] = a[a1.first][a1.second] + 1;
				Q.push(make_pair(cx, cy));
			}
		}
	}
	for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++)b[i][j] = a[i][j]; }
	for (int i = 1; i <= n; i++) { for (int j = n - 1; j >= i; j--) b[j][i] += b[j + 1][i]; }
	for (int i = n; i >= 1; i--) {
		for (int j = i; j <= n; j++) {
			c[j][i] = c[j + 1][i + 1] + b[j][i];
		}
	}
	for (int i = 0; i <= n + 1; i++) { for (int j = 0; j <= n + 1; j++) b[i][j] = 0; }
	for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) b[i][j] = a[i][j]; }
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= i; j++) b[i][j] += b[i][j - 1];
	}
	for (int i = 1; i <= n; i++) {
		for (int j = n; j >= i; j--) b[j][i] += b[j + 1][i];
	}
	for (int i = 1; i <= n + 1; i++) dp[n + 1][i] = 1;
	long long ans = 0;
	for (int i = n; i >= 1; i--) {
		for (int j = i; j >= 1; j--) {
			long long G = min(dp[i + 1][j], dp[i + 1][j + 1]);
			while (true) {
				if (sum(i, j, G) < r) { dp[i][j] = G + 1; break; }
				G--;
			}
			ans += (n - i + 1) - dp[i][j] + 1;
		}
	}
	cout << ans << endl;
	return 0;
}
0