제출 #863001

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
863001		Hosen_ba	Bigger segments (IZhO19_segments)	C++17	0 / 100	0 ms	348 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]};
    int mx=1;
    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 || dp[mid-1].first<mx){
                    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];
        }
        mx=max(mx,dp[i].first);
    }
    cout<<dp[n-1].first<<endl;
}
/*
6 
4 / 1 2 1 / 2 2
*/

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