Submission #1081812

#	Time	Username	Problem	Language	Result	Execution time	Memory
1081812		oscar1f	Jobs (BOI24_jobs)	C++17	0 / 100	2081 ms	560300 KiB

Main

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

#define int long long

const int MAX_SOM=300*1000+5;
int nbSom,argDeb;
int val[MAX_SOM],pere[MAX_SOM];
vector<int> listeFils[MAX_SOM];
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> memo[MAX_SOM];

void afficher(int pos) {
    auto temp=memo[pos];
    cout<<memo[pos].size()<<endl;
    while (!temp.empty()) {
        cout<<temp.top().first<<" "<<temp.top().second<<endl;
        temp.pop();
    }
    cout<<endl;
}

void insere(int pos,int petit) {
    while (!memo[petit].empty()) {
        memo[pos].push({memo[petit].top().first,memo[petit].top().second});
        memo[petit].pop();
    }
}

void ajout(int pos,int valAjout) {
    int gainSur=valAjout;
    while (!memo[pos].empty() and memo[pos].top().first<=gainSur) {
        gainSur+=memo[pos].top().second;
        memo[pos].pop();
    }
    memo[pos].push({0,gainSur});
}

void retrait(int pos,int valSuppr) {
    //cout<<"!!!!!"<<pos<<" "<<valSuppr<<" "<<gainSur[pos]<<endl;
    int gain=-valSuppr,dernDec=0;
    while (!memo[pos].empty() and (gain<=0 or memo[pos].top().first<valSuppr)) {
        dernDec=memo[pos].top().first;
        gain+=memo[pos].top().second;
        memo[pos].pop();
    }
    if (gain>0) {
        memo[pos].push({max(dernDec,valSuppr),gain});
    }
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin>>nbSom>>argDeb;
    for (int i=1;i<=nbSom;i++) {
        cin>>val[i]>>pere[i];
        listeFils[pere[i]].push_back(i);
    }
    val[0]=argDeb;
    for (int i=nbSom;i>=0;i--) {
        for (int j:listeFils[i]) {
            insere(i,j);
        }
        if (val[i]>0) {
            ajout(i,val[i]);
        }
        else if (val[i]<0) {
            retrait(i,-val[i]);
        }
        //afficher(i);
    }
    int argFin=0;
    while (!memo[0].empty() and argFin>=memo[0].top().first) {
        argFin+=memo[0].top().second;
        memo[0].pop();
    }
    cout<<argFin-argDeb<<endl;
    return 0;
}   
 

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