제출 #1188904

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1188904		imppppp	Jobs (BOI24_jobs)	C++20	11 / 100	101 ms	23996 KiB

Main

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

struct Task {
    int64 need;   // minimal money before the task
    int64 gain;   // net money change after finishing it
};

/* comparator that yields the optimal order for tasks with gain>0 only */
static bool pos_order(const Task& a, const Task& b)
{
    return a.need < b.need;                 // all gains are positive here
}

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

    int N;
    int64 S;
    if (!(cin >> N >> S)) return 0;

    vector<int64> profit(N + 1);
    vector<int>    parent(N + 1);
    vector<vector<int>> child(N + 1);

    for (int i = 1; i <= N; ++i) {
        cin >> profit[i] >> parent[i];
        if (parent[i] != 0) child[parent[i]].push_back(i);
    }

    vector<int64> need(N + 1), gain(N + 1);          // results for every node

    /* process nodes in decreasing index => children already done */
    for (int i = N; i >= 1; --i) {
        vector<Task> kids;
        kids.reserve(child[i].size());
        for (int v : child[i])
            if (gain[v] > 0)                         // skip useless subtrees
                kids.push_back({need[v], gain[v]});

        sort(kids.begin(), kids.end(), pos_order);   // gains are positive

        int64 cur_need  = profit[i] < 0 ? -profit[i] : 0;   // job itself
        int64 cur_gain  = profit[i];
        int64 total_need = cur_need;

        for (const Task& t : kids) {
            total_need = max(total_need, t.need - cur_gain);
            cur_gain  += t.gain;
        }
        need[i] = total_need;
        gain[i] = cur_gain;
    }

    /* independent profitable root projects */
    vector<Task> roots;
    for (int i = 1; i <= N; ++i)
        if (parent[i] == 0 && gain[i] > 0)
            roots.push_back({need[i], gain[i]});

    sort(roots.begin(), roots.end(), pos_order);

    int64 money = S;
    for (const Task& t : roots) {
        if (money < t.need) break;
        money += t.gain;
    }

    cout << (money - S) << '\n';
    return 0;
}

• Subtask 1: 11 / 11
• Subtask 2: 0 / 14
• Subtask 3: 0 / 15
• Subtask 4: 0 / 29
• Subtask 5: 0 / 31