Submission #810300

#	Time	Username	Problem	Language	Result	Execution time	Memory
810300		tosivanmak	Bigger segments (IZhO19_segments)	C++17	0 / 100	1 ms	320 KiB

segments

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



int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    ll n;
    cin>>n;
    ll arr[n+5],dp[n+5],psum[n+5];
    psum[0]=0;
    for(int i=1;i<=n;i++){
        cin>>arr[i];
        psum[i]=psum[i-1]+arr[i];
        dp[i]=0;
    }
    // psum[i]-psum[j]>=maxi_j
    // psum[i]>=maxi_j+psum[j]
    
    set<vector<ll> >st;vector<ll>dummy;
    set<vector<ll> >notok;
    dummy.push_back(0);
    dummy.push_back(0);
    dummy.push_back(0);
    st.insert(dummy);
    vector<ll>bruh;
    bruh.push_back(-1e18);
    bruh.push_back(-1e18);
    bruh.push_back(-1e18);
    for(int i=1;i<=n;i++){
            ll ck=-psum[i];
            vector<ll>v;
             v.push_back(ck);
        v.push_back(-1e18);
        v.push_back(-1e18);
        while(notok.size()){
            vector<ll> k=*notok.lower_bound(bruh);
            if(k[0]<=psum[i]){
                notok.erase(k);
                k[0]=-k[0];
                k[1]=-k[1];
                st.insert(k);
            }
            else{
                break;
            }
        }
            vector<ll> get=*st.lower_bound(v);
            dp[i]=-get[1]+1;
            vector<ll>v2;
            // cout<<get[2]<<"\n";
            // cout<<get[0]<<" "<<get[1]<<" "<<get[2]<<"\n";
            // cout<<i<<": "<<get[2]<<"\n";
            v2.push_back((psum[i]+psum[i]-psum[get[2]]));
            v2.push_back(dp[i]);
            v2.push_back(i);
            notok.insert(v2);
        
    }
    cout<<dp[n]<<"\n";
}

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