Submission #300556

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

sequence

#include <bits/stdc++.h>

using namespace std;
long long dp[1001][202]={},n,k,arr[1001]={};
void solve(long x)
{
    if(x==n){
    return;
    }
    for(long i=0;i<x;i++){
    for(long j=1;j<=k;j++){
    dp[x][j+1]=max(dp[x][j+1],dp[i][j]+((arr[n-1]-arr[x])*(arr[x]-arr[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;
    return 0;
}

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