Submission #444756

#	Time	Username	Problem	Language	Result	Execution time	Memory
444756		impri	Split the sequence (APIO14_sequence)	C++14	50 / 100	2093 ms	46064 KiB

sequence

#include<bits/stdc++.h>
using namespace std;
int n,k;
int arr[100001];
long long psum[100001];
long long dp[100001][2];
int res[100001][201];
int main(void){
cin >> n >> k;
k++;
for(int i=1;i<=n;i++)
    cin >> arr[i];
for(int i=1;i<=n;i++)
    psum[i]=psum[i-1]+arr[i];
for(int i=1;i<n;i++)
    dp[i][1]=psum[i]*(psum[n]-psum[i]);
for(int i=2;i<=k;i++){
    for(int j=i;j<=n;j++){
            long long cur=0;
     int pos=0;
        for(int u=i-1;u<j;u++){
            long long temp=dp[u][(i+1)%2]+(psum[j]-psum[u])*(psum[n]-psum[j]);
            if(temp>=cur){
                cur=temp;
                pos=u;
            }
        }
        dp[j][i%2]=cur;
        res[j][i]=pos;
    }
}
cout << dp[n][k%2] <<'\n';
int cur=n;
vector<int>r;
for(int i=k;i>1;i--){
    r.push_back(res[cur][i]);
    cur=res[cur][i];
}
for(int i=k-2;i>=0;i--)
    cout << r[i] << ' ';
}

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