結果

問題 No.655 E869120 and Good Triangles
コンテスト
ユーザー e869120
提出日時 2018-01-28 13:25:57
言語 C++14
(gcc 13.3.0 + boost 1.87.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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

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