Submission #968926

#	Time	Username	Problem	Language	Result	Execution time	Memory
968926		noyancanturk	Split the sequence (APIO14_sequence)	C++17	71 / 100	75 ms	131072 KiB

sequence

#include "bits/stdc++.h"
using namespace std;
    
#define int int64_t
#define pb push_back
    
const int lim=1e5+100;
const int mod=1e9+7;
    
using pii=pair<int,int>;
    
void solve(){
    int n,k;
    cin>>n>>k;
    int a[n+1];
    a[0]=0;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        a[i]+=a[i-1];
    }
    int dp[k+1][n+1];
    memset(dp,0,sizeof(dp));
    #define b(x) (dp[i-1][x]-a[x]*a[x])
    for(int i=1;i<=k;i++){
        deque<int>h;
        h.pb(i);
        for(int j=i+1;j<=n;j++){
            int sz;
            while(1<(sz=h.size())&&
                b(h[sz-1])+a[j]*a[h[sz-1]]
                <=
                b(h[sz-2])+a[j]*a[h[sz-2]]
            )h.pop_back();
            dp[i][j]=b(h[sz-1])+a[j]*a[h[sz-1]];
            while(1<h.size()&&
                (b(j)-b(h[0]))*(a[h[0]]-a[h[1]])
                >=
                (b(h[1])-b(h[0]))*(a[h[0]]-a[j])
            )h.pop_front();
            h.push_front(j);
        }
    }
    int ans=dp[k][n];
    cout<<ans<<"\n";
    int r=n;
    for(int i=n-1;0<=i;i--){
        if((a[r]-a[i])*a[i]+dp[k-1][i]==ans){
            cout<<i<<" ";
            ans-=(a[r]-a[i])*a[i];
            r=i;
            k--;
        }
        if(ans==0)break;
    }
}
    
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
#ifdef Local  
    freopen(".in","r",stdin);
    freopen(".out","w",stdout);
#endif
    int t=1;
    //cin>>t;
    while (t--)
    {
        solve();
    }
}

• Subtask 1: 11 / 11
• Subtask 2: 11 / 11
• Subtask 3: 11 / 11
• Subtask 4: 17 / 17
• Subtask 5: 21 / 21
• Subtask 6: 0 / 29