제출 #706886

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
706886		safaricola	Bigger segments (IZhO19_segments)	C++17	0 / 100	1 ms	340 KiB

segments

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> ii;
#define eb emplace_back
#define pb push_back
#define mp make_pair
#define f first
#define s second
#define rep(i,n) for(ll i = 1; i <= n; i++)
ll n, a[500010],k[500010],s[500010],st[500010];
ii dp[500010];
int main(){
    cin>>n;
    rep(i,n)cin>>a[i],s[i]=s[i-1]+a[i];
    dp[1]={1,a[1]};
    k[1]=1;
    st[1]=1;
    int K=1;
    for(int i=2; i<=n; i++){
        //make a new group
        while(k[K]+1<i&&dp[k[K]+1].s<s[i]-s[k[K]+1]){
            k[K]++;
        }
        if(dp[st[K]].s<=s[i]-s[k[K]]){
            dp[i]={K+1,s[i]-s[k[K]]};
            K++;
            st[K]=i;
            k[K]=i;
        //cout<<">"<<dp[i].f<<' '<<dp[i].s<<endl;
            continue;
        }
        dp[i]={K,1e9};
        // get min from K-1;
        while(k[K-1]+1<st[K]&&dp[k[K-1]+1].s<s[i]-s[k[K-1]+1]){
            k[K-1]++;
        }
        if(dp[k[K-1]].s<s[i]-s[k[K-1]]){
            dp[i].s=s[i]-s[k[K-1]];
        }
        //add on to k
        dp[i].s=min(dp[i].s,dp[i-1].s+a[i]);
        //cout<<dp[i].f<<' '<<dp[i].s<<endl;
    }
    cout<<K<<endl;
}

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