結果
問題 |
No.655 E869120 and Good Triangles
|
ユーザー |
|
提出日時 | 2025-08-06 13:14:40 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 960 ms / 2,500 ms |
コード長 | 2,874 bytes |
コンパイル時間 | 2,144 ms |
コンパイル使用メモリ | 212,056 KB |
実行使用メモリ | 449,832 KB |
最終ジャッジ日時 | 2025-08-06 13:15:01 |
合計ジャッジ時間 | 8,445 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 30 |
ソースコード
#include <bits/stdc++.h> #define int ll #define fi first #define endl '\n' #define il inline #define se second #define pb push_back #define INF 0x3f3f3f3f using namespace std; typedef long long ll; typedef pair<int, int> pii; #ifdef ONLINE_JUDGE #define debug(...) 0 #else #define debug(...) fprintf(stderr, __VA_ARGS__), fflush(stderr) #endif const int N = 1e5 + 10; int n, k, p; signed main() { ios::sync_with_stdio(0); cin.tie(0), cout.tie(0); cin >> n >> k >> p; vector<vector<int>> a(n, vector<int>(n, INF)); deque<pair<int, int>> q; for (int i = 0, x, y; i < k; i++) cin >> x >> y, x--, y--, q.pb({x, y}), a[x][y] = 0; while (!q.empty()) { int x = q.front().fi; int y = q.front().se; q.pop_front(); if (0 <= y - 1 && y - 1 <= x - 1 && x-1<n && a[x][y] + 1 < a[x - 1][y - 1]) a[x - 1][y - 1] = a[x][y] + 1, q.pb({x - 1, y - 1}); if (0 <= y && y <= x - 1 && x-1<n && a[x][y] + 1 < a[x - 1][y]) a[x - 1][y] = a[x][y] + 1, q.pb({x - 1, y}); if (0 <= y - 1 && y - 1 <= x && x<n && a[x][y] + 1 < a[x][y - 1]) a[x][y - 1] = a[x][y] + 1, q.pb({x, y - 1}); if (0 <= y + 1 && y + 1 <= x && x<n && a[x][y] + 1 < a[x][y + 1]) a[x][y + 1] = a[x][y] + 1, q.pb({x, y + 1}); if (0 <= y && y <= x + 1 && x+1<n && a[x][y] + 1 < a[x + 1][y]) a[x + 1][y] = a[x][y] + 1, q.pb({x + 1, y}); if (0 <= y + 1 && y + 1 <= x + 1 && x+1<n && a[x][y] + 1 < a[x + 1][y + 1]) a[x + 1][y + 1] = a[x][y] + 1, q.pb({x + 1, y + 1}); } vector<vector<int>> L(n, vector<int>(n)); vector<vector<int>> R(n, vector<int>(n)); for (int i = 0; i < n; i++) for (int j = 0; j <= i; j++) L[i][j] = a[i][j] + (i > 0 ? L[i - 1][j] : 0); for (int i = 0; i < n; i++) for (int j = 0; j <= i; j++) R[i][j] = a[i][j] + (j > 0 && i>0 ? R[i - 1][j - 1] : 0); for (int i = 0; i < n; i++) { a[i].insert(a[i].begin(), 0); for (int j = 1; j <= i + 1; j++) a[i][j] += a[i][j - 1]; } int ans = 0; vector<pair<int, int>> f(n + 1, {0, 0}); for (int i = 0; i < n; i++) { vector<pair<int, int>> g = f; f = vector<pair<int, int>>(i + 2, {0, 0}); for (int j = 0; j <= i; j++) { int ii = g[j].fi, s = g[j].se; while (ii < n && s < p) s += a[ii][j - i + ii + 1] - a[ii][j], ii++; g[j] = {ii, s}; if (i != n - 1) { f[j] = max(f[j], {ii, s - (R[ii - 1][j - i + ii - 1] - (i > 0 && j > 0 ? R[i - 1][j - 1] : 0))}); f[j + 1] = max(f[j + 1], {ii, s - (L[ii - 1][j] - (i > 0 && i != j ? L[i - 1][j] : 0))}); } } for (int j = 0; j <= i; j++) if (g[j].se >= p) ans += n - g[j].fi + 1; } cout << ans << endl; return 0; }