Submission #300567

#	Time	Username	Problem	Language	Result	Execution time	Memory
300567		NicolaAbusaad2014	Split the sequence (APIO14_sequence)	C++14	50 / 100	120 ms	3712 KiB

sequence

#include <bits/stdc++.h>

using namespace std;
long long dp[1001][202]={},n,k,arr[1001]={},from[1001][202]={};
void solve(long x)
{
    if(x==n){
    return;
    }
    for(long i=0;i<x;i++){
    for(long j=1;j<=k;j++){
    if(dp[i][j]+((arr[n-1]-arr[x])*(arr[x]-arr[i]))>dp[x][j+1]){
    dp[x][j+1]=dp[i][j]+((arr[n-1]-arr[x])*(arr[x]-arr[i]));
    from[x][j+1]=i;
    }
    }
    }
    solve(x+1);
}
int main()
{
    long long x;
    cin>>n>>k;
    cin>>x;
    arr[0]=x;
    for(long i=1;i<n;i++){
    cin>>x;
    arr[i]=arr[i-1]+x;
    }
    for(long i=0;i<n;i++){
    dp[i][1]=arr[i]*(arr[n-1]-arr[i]);
    }
    solve(1);
    cout<<dp[n-1][k+1]<<endl;
    long now=from[n-1][k+1];
    stack<long>s;
    for(long i=0;i<k;i++){
    s.push(now);
    now=from[now][k-i];
    }
    while(!s.empty()){
    cout<<s.top()+1<<endl;
    s.pop();
    }
    return 0;
}

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