Submission #889519

#	Time	Username	Problem	Language	Result	Execution time	Memory
889519		White	Bigger segments (IZhO19_segments)	C++14	0 / 100	1 ms	4596 KiB

segments

#include <bits/stdc++.h>
#define endl "\n"
using namespace std;

pair<long long,long long> dp[500005];
long long sum[500005],red[500005];

long long binary(long long now){
    long long l=0,r=now,mid;
    dp[now]={1000000000000007,0};
    while(l<r){
        mid=(l+r)/2;
        long long s;
        s=sum[mid];
        if(sum[r]-s>=dp[mid].first)l=mid+1;
        else r=mid;
        //cout<<l<<"_"<<r<<endl;
    }
    return l;
}

int main(){

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    long long n;
    cin>>n;
    cin>>red[0];
    sum[0]=red[0];
    for(int i=1;i<n;i++){
        cin>>red[i];
        sum[i]=sum[i-1]+red[i];
    }

    dp[0]={red[0],1};
    for(int i=1;i<n;i++){
        long long index=binary(i);
        if(index==0){
            if(sum[i]-red[0]>=red[0])dp[i]={sum[i]-red[i],2};
            else dp[i]={sum[i],1};
        }
        else if (index<i){
            if(sum[i]-sum[index-1]>=dp[index-1].first) dp[i]={sum[i]-sum[index-1],dp[index-1].second+1};
            else dp[i]={sum[i]-sum[index-1]+dp[index-1].first,dp[index-1].second};
        }
        else if (index==i && red[i]>=dp[i-1].first)dp[i]={red[i],dp[i-1].second+1};
        else dp[i]={red[i]+dp[i-1].first,dp[i-1].second};
                //cout<<index<<" - "<<i<<": "<<dp[i].first<<" "<<dp[i].second<<endl;

    }
    cout<<dp[n-1].second<<endl;

    return 0;
}

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