mayoko’s diary

プロコンとかいろいろ。

Codeforces Round #325 (Div. 1) A. Gennady the Dentist

あまりの問題文の長さに撤退してしまったこどふぉ。ただ最近言い訳ばっかして Splatoon やってるだけなのでちょっと頑張らないといけないですね〜

解法

子供の診察順に処理していきます。

i 番目の子の治療ができるかを確かめるために, まず i 以降の子が出て行かないかをチェックします。下のコードを見るとこれは O(N^3) かかっているように見えますが, k を使った for 文は, N 回しか回されないことが保証される(それぞれの子が出て行くタイミングは 1 回しかないので)ので, O(N^2) です。

その後, i 番目の子を治療できる場合は問題文に書いてあるような処理をします。

const int MAXN = 4044;
int n;
ll v[MAXN], d[MAXN], p[MAXN];
bool ok[MAXN];

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> v[i] >> d[i] >> p[i];
    }
    for (int i = 0; i < n; i++) ok[i] = true;
    vector<int> ans;
    for (int i = 0; i < n; i++) {
        int flag = 1;
        while (flag) {
            flag = 0;
            for (int j = i; j < n; j++) {
                if (p[j] < 0 && ok[j]) {
                    flag = 1;
                    ok[j] = false;
                    for (int k = j+1; k < n; k++) p[k] -= d[j];
                }
            }
        }
        if (p[i] >= 0) {
            ans.push_back(i+1);
            int cnt = v[i], j = i+1;
            while (j < n && cnt > 0) {
                if (ok[j]) {
                    p[j] -= cnt--;
                }
                j++;
            }
        }
    }
    cout << ans.size() << endl;
    for (int el : ans) cout << el << " ";
    cout << endl;
    return 0;
}