Submission #862962

#	Time	Username	Problem	Language	Result	Execution time	Memory
862962		Hosen_ba	Bigger segments (IZhO19_segments)	C++17	13 / 100	1 ms	600 KiB

segments

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
    int n;
    cin>>n;
    int a[n+2];
    ll p[n+2];
    ll s=0;
    for(int i=0;i<n;i++){
        cin>>a[i];
        s+=a[i];
        p[i]=s;
    }
    pair<int,ll>dp[n];
    dp[0]={1,a[0]};
    for(int i=1;i<n;i++){
        int l=0,r=i;
        while(l<r){
            int mid=(l+r+1)/2;
            bool f=true;
            if(mid){
                f=false;
                ll s=p[i];
                s-=p[mid-1];
                if(s>=dp[mid-1].second){
                    f=true; 
                }
            }
            if(f){
                l=mid;
            }else{
                r=mid-1;
            }
        }
        dp[i].first=1;
        dp[i].second=p[i];
        if(l){
            dp[i].first=dp[l-1].first+1;
            dp[i].second-=p[l-1];
        }
    }
    cout<<dp[n-1].first<<endl;
}

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