結果
問題 | No.655 E869120 and Good Triangles |
ユーザー |
|
提出日時 | 2018-02-24 00:00:43 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,889 ms / 2,500 ms |
コード長 | 2,759 bytes |
コンパイル時間 | 1,042 ms |
コンパイル使用メモリ | 86,392 KB |
実行使用メモリ | 316,672 KB |
最終ジャッジ日時 | 2024-10-10 02:40:21 |
合計ジャッジ時間 | 35,039 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 30 |
ソースコード
#include <iostream> #include <algorithm> #include <vector> #include <queue> using namespace std; int main() { int n, K; long long p; cin >> n >> K >> p; vector<vector<int>> dist(n, vector<int>(n, -1)); queue<pair<int, int>> q; for (int i = 0; i < K; i++) { int y, x; cin >> y >> x; y--; x--; dist[y][x] = 0; q.emplace(y, x); } while (!q.empty()) { int y = q.front().first; int x = q.front().second; q.pop(); int dy[] = {1, 1, 0, -1, -1, 0}; int dx[] = {0, 1, 1, 0, -1, -1}; for (int k = 0; k < 6; k++) { int ny = y + dy[k]; int nx = x + dx[k]; if (ny < 0 || nx < 0 || nx > ny || ny >= n) continue; if (dist[ny][nx] == -1) { dist[ny][nx] = dist[y][x] + 1; q.emplace(ny, nx); } } } for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (dist[i][j] == -1) dist[i][j] = 0; } } #ifdef FOO for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { cout << dist[i][j]; cout << ' '; } cout << endl; } cout << endl; #endif vector<vector<long long>> sum(n + 1, vector<long long>(n + 1)); for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { sum[i + 1][j + 1] = dist[i][j] + sum[i + 1][j] + sum[i][j + 1] - sum[i][j]; } } #ifdef FOO for (int i = 0; i <= n; i++) { for (int j = 0; j <= n; j++) { cout << sum[i][j]; cout << ' '; } cout << endl; } cout << endl; #endif vector<vector<long long>> tri(n, vector<long long>(n)); for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { tri[i][j] = dist[i][j]; if (i - 1 >= 0 && j - 1 >= 0) { tri[i][j] += tri[i - 1][j - 1]; } if (j - 1 >= 0) { tri[i][j] += tri[i][j - 1]; } if (i - 1 >= 0 && j - 2 >= 0) { tri[i][j] -= tri[i - 1][j - 2]; } } } #ifdef FOO for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { cout << tri[i][j]; cout << ' '; } cout << endl; } cout << endl; #endif long long ans = 0; for (int i = 0; i < n; i++) { for (int j = 0; j <= i; j++) { int ng = i - 1; int ok = n; auto f = [&](int k) { int d = k - i; long long hoge = tri[k][j + d]; hoge -= sum[k + 1][j] - sum[i + 1][j]; hoge -= tri[i][j]; hoge += dist[i][j]; return hoge; }; while (ok - ng > 1) { int mid = (ok + ng) / 2; if (f(mid) >= p) { ok = mid; } else { ng = mid; } } #ifdef FOO for (int k = ok; k < n; k++) { printf("%d %d %d %lld\n", i, j, k, f(k)); } #endif ans += n - ok; } } cout << ans << endl; }