Submission #1063222

#	Time	Username	Problem	Language	Result	Execution time	Memory
1063222		anton	Jobs (BOI24_jobs)	C++17	29 / 100	160 ms	28912 KiB

Main

#include<bits/stdc++.h>

using namespace std;

#define int long long 
#define pii pair<int, int>
const int MAX_N = 3e5+1;
int N, S;

vector<vector<int>> seq;

signed main(){
    cin>>N>>S;

    for(int i = 0; i<N; i++){
        int x, p;
        cin>>x>>p;
        if(i>0 && p==i){
            seq.back().push_back(x);
        }
        else{
            seq.push_back({x});
        }
    }

    vector<pii> pq;

    for(auto s: seq){
        int prev_max =0;
        int pref_s = 0;
        int min_on_path = 1e18;

        for(auto e: s){
            pref_s+=e;

            min_on_path = min(min_on_path, pref_s);
            if(pref_s>prev_max){
                pq.push_back({min_on_path-prev_max, pref_s-prev_max});
                prev_max=  pref_s;
            }
        }
    }

    int initS = S;

    sort(pq.begin(), pq.end());
    

    while(pq.size()>0){
        pii e  = pq.back();
        pq.pop_back();
        if(S+e.first<0){
            break;
        }
        else{
            S+= e.second;
        }
    }

    cout<<S-initS<<endl;


    

}

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