Submission #168427

#	Time	Username	Problem	Language	Result	Execution time	Memory
168427		IldarKA	Bigger segments (IZhO19_segments)	C++14	100 / 100	518 ms	44280 KiB

segments

#include <bits/stdc++.h>

using namespace std;
int n, a[500001], dp[500001];
long long pr[500001], seg[500001];
int main(){
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
        pr[i] = pr[i - 1] + a[i];
    }
    set < pair < long long, int > > s;
    s.insert({0, 0});
    for(int i = 1; i <= n; i++){
        int j = 0;
        while(!s.empty()){
            if((s.begin()->first) > pr[i]) break;
            j = max(j, s.begin() -> second);
            s.erase(s.begin());
        }
        dp[i] = dp[j] + 1;
        seg[i] = pr[i] - pr[j];
        s.insert({pr[j] + seg[j], j});
        s.insert({pr[i] + seg[i], i});
    }
    cout << dp[n];
}

• Subtask 1: 13 / 13
• Subtask 2: 14 / 14
• Subtask 3: 10 / 10
• Subtask 4: 36 / 36
• Subtask 5: 27 / 27