Submission #370068

#	Time	Username	Problem	Language	Result	Execution time	Memory
370068		wildturtle	Bigger segments (IZhO19_segments)	C++14	100 / 100	277 ms	20944 KiB

segments

#include<bits/stdc++.h>
using namespace std;
long long a,b,c,d,i,e,f,g,n,m,k,l,A[500005],B[500005],ans,mid,le,ri;
pair <long long,long long> dp[500005];
int main() {
    cin>>n;
    for(long long i=1;i<=n;i++) {
        cin>>A[i];
        B[i]=A[i]+B[i-1];
        dp[i]={1,-B[i]};
    }
    for(long long i=1;i<n;i++) {
        dp[i+1]=max(dp[i+1],{dp[i].first,dp[i].second-A[i+1]});
        //cout<<i+1<<" "<<dp[i+1].first<<" "<<-dp[i+1].second<<endl;
        le=i+1; ri=n; ans=-1;
        while(le<=ri) {
            mid=(le+ri)/2;
            if(B[mid]-B[i]>=-dp[i].second) { ans=mid; ri=mid-1; }
            else le=mid+1;
        }
        if(ans==-1) continue;
        dp[ans]=max(dp[ans],{dp[i].first+1,-B[ans]+B[i]});
        //cout<<ans<<" "<<dp[ans].first<<" "<<-dp[ans].second<<endl;
    }
    cout<<dp[n].first;
}

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