Submission #691592

#	Time	Username	Problem	Language	Result	Execution time	Memory
691592		White	Bigger segments (IZhO19_segments)	C++14	37 / 100	1592 ms	2708 KiB

segments

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#define endl "\n"
using namespace std;

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

int main(){

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


    long long n;
    cin>>n>>red[0];
    sum[0]=red[0];
    for(int i=1;i<n;i++){
        cin>>red[i];
        sum[i]=sum[i-1]+red[i];
    }
    ans[0]={1,red[0]};
    for(int i=1;i<n;i++){
        ans[i]={ans[i-1].first,ans[i-1].second+red[i]};
        for(int j=i-1;j>=0 && ans[i].first-ans[j].first<2;j--){
            if(ans[i].first-ans[j].first==0){
                if(ans[j].second<=sum[i]-sum[j]){
                    ans[i]={ans[j].first+1,sum[i]-sum[j]};
                    break;
                }
            }else{
                if(ans[j].second<=sum[i]-sum[j] && sum[i]-sum[j]<ans[i].second){
                    ans[i]={ans[j].first+1,sum[i]-sum[j]};
                    j=-1;
                    break;
                }
            }
        }
    }
    cout<<ans[n-1].first<<endl;

    return 0;
}

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