Submission #1003510

#	Time	Username	Problem	Language	Result	Execution time	Memory
1003510		0pt1mus23	Split the sequence (APIO14_sequence)	C++14	39 / 100	2039 ms	131072 KiB

sequence

#pragma GCC optimize("O3", "inline")
#include <bits/stdc++.h>
using namespace std;
#define ins insert
#define pb push_back
#define int long long int
#define pii pair<int, int>
#define endl '\n'
#define drop(x) cout<<(x)<<endl; return;
#define all(x) x.begin(),x.end()
const int mod = 1e9 +7, sze = 1e5, inf = 2e18, prime = 23;

int dp[sze][205];
int par[sze][205];
void mal(){
    int n,k;
    cin>>n>>k;
    vector<int> pref(n+1,0);
    vector<int> arr(n+1);
    for(int i=1;i<=n;i++){
        cin>>arr[i];
        pref[i]=pref[i-1]+arr[i];
    }
    for(int j=1;j<n;j++){
        dp[j][1] = (pref[n] - pref[j] ) * (pref[j]);
    }
    for(int i=2;i<n;i++){
        for(int j=2;j<=k;j++){
            for(int p=1;p<i;p++){
                int  x=dp[p][j-1] + (pref[n]-pref[i]) * (pref[i] - pref[p]);
                if(x>=dp[i][j]){
                    dp[i][j]=x;
                    par[i][j]=p;
                }
            }
        }
    }
    int mx =0;
    int p =0;
    int kk = k;
    for(int i=1;i<=n;i++){
        if(dp[p][k]<dp[i][k]){
            p=i;
        }
        mx=max(mx, dp[i][k]);
    }
    vector<int> pat;
    while(p){
        pat.pb(p);
        p = par[p][kk--];
    }
    reverse(all(pat));
    cout<<mx<<endl;
    for(auto v:pat){
        cout<<v<<" ";
    }
    cout<<endl;

}   

signed main() {
    cin.tie(0)->sync_with_stdio(0);
    int tt = 1;
    // cin>>tt;
    
    while(tt--){
        mal();        
    }
}

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