Submission #712987

#	Time	Username	Problem	Language	Result	Execution time	Memory
712987		bin9638	Split the sequence (APIO14_sequence)	C++17	71 / 100	78 ms	33868 KiB

sequence

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define pb push_back
#define N 10010
#define ii pair<ll,int>
#define fs first
#define sc second
#define ld double
#define int ll

void selfmax(int&u,int v)
{
    u=max(u,v);
}

int dp[N][210],n,k,sum[N];

void solve(int l,int r,int best_l,int best_r,int t)
{
    int res=-1e18,mid=(l+r)/2,vt=0;
    for(int i=best_l;i<min(best_r+1,mid);i++)
        if(dp[i][t-1]+sum[i]*(sum[mid]-sum[i])>res)
        {
            res=dp[i][t-1]+sum[i]*(sum[mid]-sum[i]);
            vt=i;
        }
    //cout<<l<<" "<<r<<" "<<best_l<<" "<<best_r<<" "<<mid<<" "<<res<<endl;
    dp[mid][t]=res;
    if(l<mid)
        solve(l,mid-1,best_l,vt,t);
    if(mid<r)
        solve(mid+1,r,vt,best_r,t);
}

int32_t main()
{
    #ifdef SKY
    freopen("A.inp","r",stdin);
    freopen("A.out","w",stdout);
    #endif // SKY
    ios::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
    cin>>n>>k;
    for(int i=1;i<=n;i++)
        cin>>sum[i],sum[i]+=sum[i-1];
    memset(dp,-0x3f3f,sizeof(dp));
    for(int i=1;i<=n;i++)
        dp[i][0]=0;
    for(int t=1;t<=k;t++)
        solve(t+1,n,t,n,t);
    cout<<dp[n][k]<<endl;
    int vt=n;
    for(int t=k;t>=1;t--)
    {
        for(int i=t;i<vt;i++)
            if(dp[i][t-1]+sum[i]*(sum[vt]-sum[i])==dp[vt][t])
            {
                cout<<i<<" ";
                vt=i;
                break;
            }
    }
}

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