結果

問題 No.3220 Forest Creation
ユーザー jiangxinyang
提出日時 2025-08-01 22:20:40
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,836 bytes
コンパイル時間 2,056 ms
コンパイル使用メモリ 200,892 KB
実行使用メモリ 7,716 KB
最終ジャッジ日時 2025-08-01 22:20:44
合計ジャッジ時間 4,168 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 22 WA * 23
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll mod = 1e9 + 7;
const int N = 200005;
const int INF = 0x3f3f3f3f;
ll a[N];
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    for (int i = 0; i <= n; i++) cin >> a[i];
    ll tot = 0, sum = 0;
    for (int i = 1; i <= n; i++) {
        tot += a[i];
        sum += 1ll * a[i] * i;
    }
    if ((sum & 1) || sum > 2 * (tot - 1)) {
        cout << "No\n";
        return 0;
    }
    if (tot <= n) {
        for (int i = tot; i <= n; i++) {
            if (a[i] > 0) {
                cout << "No\n";
                return 0;
            }
        }
    }
    vector<int> vec;
    vector<ll> cnt;
    for (int i = n; i >= 0; i--) {
        if (a[i] > 0) {
            vec.push_back(i);
            cnt.push_back(a[i]);
        }
    }
    int m = (int)vec.size();
    vector<ll> pc(m), ps(m);
    for (int i = 0; i < m; i++) {
        pc[i] = cnt[i] + (i ? pc[i - 1] : 0);
        ps[i] = cnt[i] * vec[i] + (i ? ps[i - 1] : 0);
    }
    for (int t = 0; t < m; t++) {
        ll res = pc[t] * (pc[t] - 1);
        if (pc[t] < 0 || pc[t] > tot) {
            cout << "No\n";
            return 0;
        }
        if (t == m - 1) {
        } else {
            int l = t + 1, r = m;
            while (l < r) {
                int mid = l + r >> 1;
                if (vec[mid] > pc[t])
                    l = mid + 1;
                else
                    r = mid;
            }
            int p = l;
            ll v1 = (p - 1 >= t + 1) ? (pc[p - 1] - pc[t]) : 0;
            ll v2 = ps[m - 1] - (p - 1 >= 0 ? ps[p - 1] : 0);
            res += v1 * pc[t] + v2;
        }
        if (ps[t] > res) {
            cout << "No\n";
            return 0;
        }
    }
    cout << "Yes\n";
    return 0;
}
0