Submission #976713

#	Time	Username	Problem	Language	Result	Execution time	Memory
976713		tamir1	Split the sequence (APIO14_sequence)	C++17	0 / 100	2021 ms	5212 KiB

sequence

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,k,i,j,l,a[100001],dp[201][100001],sum[100001],s,ans;
vector<ll> v;
int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin >> n >> k;
	for(i=1;i<=n;i++){
		cin >> a[i];
		sum[i]=sum[i-1]+a[i];
	}
	for(l=1;l<=k;l++){
		for(i=l;i<=n;i++){
			for(j=l-1;j<i;j++){
				dp[l][i]=max(dp[l][i],dp[l-1][j]+(sum[n]-sum[i])*(sum[i]-sum[j]));
			}
		}
	}
	for(i=k;i<=n;i++) ans=max(ans,dp[k][i]);
	cout << ans;
}

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