Submission #1080752

#	Time	Username	Problem	Language	Result	Execution time	Memory
1080752		oscar1f	Jobs (BOI24_jobs)	C++17	29 / 100	107 ms	15824 KiB

Main

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

#define int long long

struct propo {
    int gain,argMin,debSuiv,finSuiv;
    bool operator < (const propo& autre) const {
        return argMin>autre.argMin;
    }
};

const int MAX_SOM=300*1000+5;
int nbSom,argDeb;
int val[MAX_SOM],pere[MAX_SOM];
priority_queue<propo> possi;

void calc(int deb,int fin) {
    if (deb>fin) {
        return;
    }
    int somCour=0,maxDeficit=0;
    for (int i=deb;i<=fin;i++) {
        somCour+=val[i];
        maxDeficit=min(maxDeficit,somCour);
        if (somCour>0) {
            //cout<<"!"<<deb<<" "<<i<<endl;
            possi.push({somCour,-maxDeficit,i+1,fin});
            return;
        }
    }
    //cout<<deb<<" "<<fin<<endl;
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin>>nbSom>>argDeb;
    int deb=1;
    for (int i=1;i<=nbSom;i++) {
        cin>>val[i]>>pere[i];
        if (pere[i]==0) {
            calc(deb,i-1);
            deb=i;
        }
    }
    calc(deb,nbSom);
    int argCour=argDeb;
    propo nouv;
    while (!possi.empty()) {
        nouv=possi.top();
        possi.pop();
        if (argCour>=nouv.argMin) {
            argCour+=nouv.gain;
            calc(nouv.debSuiv,nouv.finSuiv);
        }
    }
    cout<<argCour-argDeb<<endl;
    return 0;
}
 

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