Submission #1253864

#	Time	Username	Problem	Language	Result	Execution time	Memory
1253864		skibidihehe	Jobs (BOI24_jobs)	C++20	0 / 100	332 ms	37376 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define ll long long
#define ull unsigned long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define taskname ""
#define ld long double

int N;
ll s;
vector<ll> x;
vector<vector<int>> ch;

// returns (ptr to multiset of chosen profits in subtree, sum of that multiset)
pair<multiset<ll>*, ll> dfs(int u){
    multiset<ll>* ms = new multiset<ll>();
    ll sum = 0;
    // merge children
    for(int v: ch[u]){
        auto [cset, csum] = dfs(v);
        // merge smaller into larger
        if(ms->size() < cset->size()){
            swap(ms, cset);
            swap(sum, csum);
        }
        // now *ms is the bigger one
        for(ll v2 : *cset){
            ms->insert(v2);
        }
        sum += csum;
        delete cset;
    }
    // add this node’s profit
    ms->insert(x[u]);
    sum += x[u];
    // if we dip below 0, drop the worst loss
    if(sum < 0){
        auto it = ms->begin();
        sum -= *it;
        ms->erase(it);
    }
    return {ms, sum};
}

int main(){
    if(fopen(taskname".inp","r")){
        freopen(taskname".inp","r",stdin);
        freopen(taskname".out","w",stdout);
    }
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> N >> s;
    x.assign(N+1, 0);
    ch.assign(N+1, {});

    // dummy root 0 gets initial capital
    x[0] = s;

    for(int i = 1; i <= N; i++){
        int p;
        cin >> x[i] >> p;
        ch[p].pb(i);
    }

    // run DP from dummy root 0
    auto [rootSet, rootSum] = dfs(0);
    // rootSum >= 0 by construction; it equals s + (sum of chosen real jobs)
    ll answer = rootSum - s;
    cout << answer;

    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:51:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   51 |         freopen(taskname".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:52:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   52 |         freopen(taskname".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

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