Submission #657926

#	Time	Username	Problem	Language	Result	Execution time	Memory
657926		Tenis0206	Split the sequence (APIO14_sequence)	C++11	100 / 100	1622 ms	84224 KiB

sequence

#include <bits/stdc++.h>
#define int long long
 
using namespace std;
 
const int oo = INT_MAX;
 
int n,k;
int v[100005];
 
int sp[100005];
 
int dp[100005][2];
signed l[100005][205];
 
int sum(int st, int dr)
{
    if(st > dr)
    {
        return 0;
    }
    return sp[dr] - sp[st - 1];
}
 
void divide(int st, int dr, int min_chosen, int max_chosen, int j)
{
    if(st > dr)
    {
        return;
    }
    int mij = (st + dr) >> 1;
    dp[mij][j % 2] = -oo;
    for(int p=min_chosen; p<=min(max_chosen,mij); p++)
    {
        if(dp[p-1][(j-1) % 2] + sum(p,mij) * sum(mij + 1, n) >= dp[mij][j % 2])
        {
            dp[mij][j % 2] = dp[p-1][(j-1) % 2] + sum(p,mij) * sum(mij + 1, n);
            l[mij][j] = p - 1;
        }
    }
    divide(st,mij-1,min_chosen,l[mij][j] + 1,j);
    divide(mij+1,dr,l[mij][j]+1,max_chosen,j);
}
 
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>k;
    ++k;
    for(int i=1; i<=n; i++)
    {
        cin>>v[i];
        sp[i] = sp[i-1] + v[i];
    }
    for(int i=1; i<=n; i++)
    {
        dp[i][1] = sum(1,i) * sum(i + 1, n);
    }
    for(int j=2; j<=k; j++)
    {
        divide(1,n,1,n,j);
    }
    cout<<dp[n][k % 2]<<'\n';
    int poz = n;
    vector<int> rez;
    while(poz)
    {
        poz = l[poz][k--];
        if(poz)
        {
            rez.push_back(poz);
        }
    }
    reverse(rez.begin(),rez.end());
    for(auto it : rez)
    {
        cout<<it<<' ';
    }
    cout<<'\n';
    return 0;
}

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