結果

問題 No.655 E869120 and Good Triangles
ユーザー vjudge1
提出日時 2025-07-27 15:22:09
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,111 ms / 2,500 ms
コード長 2,874 bytes
コンパイル時間 1,722 ms
コンパイル使用メモリ 179,040 KB
実行使用メモリ 449,792 KB
最終ジャッジ日時 2025-07-27 15:22:33
合計ジャッジ時間 20,913 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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;
}
0