oj.uz

Submission #1063065

# Submission time Handle Problem Language Result Execution time Memory
1063065 2024-08-17T13:50:20 Z anton Jobs (BOI24_jobs) C++17
0 / 100
 178 ms 27160 KB 
#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});
        }
    }

    priority_queue<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({ min_on_path, pref_s-prev_max});
                prev_max=  pref_s;
            }
        }
    }

    int initS = S;
    

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

    cout<<S-initS<<endl;


    

}

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 178 ms 27160 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 178 ms 27160 KB Output isn't correct
2 Halted 0 ms 0 KB -