結果

問題 No.3220 Forest Creation
ユーザー woshinailong
提出日時 2025-08-01 22:24:30
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,387 bytes
コンパイル時間 2,033 ms
コンパイル使用メモリ 203,312 KB
実行使用メモリ 7,720 KB
最終ジャッジ日時 2025-08-01 22:24:34
合計ジャッジ時間 3,260 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 43 WA * 2
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;
    vector<ll> A(N+1);
    for(int i = 0; i <= N; i++){
        cin >> A[i];
    }

    // 总点数 n，总度数 M
    ll n = 0, M = 0;
    for(int d = 0; d <= N; d++){
        n += A[d];
        M += (ll)d * A[d];
    }
    // 必须是偶数，且 ≤ 2(n-1) （forest 无环要求）
    if (M % 2 || M > 2*(n-1)) {
        cout << "No\n";
        return 0;
    }

    // 收集所有出现过的度，并按度从大到小
    vector<pair<int,ll>> degs;
    for(int d = 0; d <= N; d++){
        if (A[d] > 0) degs.emplace_back(d, A[d]);
    }
    sort(degs.begin(), degs.end(),
         [&](auto &x, auto &y){ return x.first > y.first; });

    // 前缀：K 个点，度和 sumL；后缀度和 totalSum
    ll K = 0, sumL = 0, totalSum = M;
    for(auto &blk : degs){
        int d = blk.first;
        ll cnt = blk.second;

        // 把整个“度 = d”这一块加入前缀
        K     += cnt;
        sumL  += (ll)d * cnt;
        totalSum -= (ll)d * cnt;

        // EG 在 k=K 处要 sumL ≤ K*(K-1) + sum_{剩余} d_j
        ll rhs = K*(K-1) + totalSum;
        if (sumL > rhs) {
            cout << "No\n";
            return 0;
        }
    }

    // 全部通过
    cout << "Yes\n";
    return 0;
}
0