Submission #25166

#	Time	Username	Problem	Language	Result	Execution time	Memory
25166		RezwanArefin01	Split the sequence (APIO14_sequence)	C++14	0 / 100	2000 ms	33800 KiB

sequence

//Bismillahir Rahmanir Rahim
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 10020, K = 202; 
ll dp[K][N], par[K][N], arr[N], p[N];

int main(int argc, char const *argv[]) {
#ifdef LOCAL_TESTING
	freopen("in", "r", stdin);
#endif 	
	int n, kk; cin>>n>>kk;
	for(int i=1; i <= n; i++) {
		cin>>arr[i]; 
		p[i] = p[i-1] + arr[i];
	}
	assert(kk != 1);;
	for(int k=1; k <= kk; k++) {
		for(int i=1; i<=n; i++) {
			par[k][i] = -1;
			for(int j=0; j<i; j++) {
				ll op = (dp[k-1][j] + (p[i] - p[j]) * p[j]);
				if(op > dp[k][i]) {
					dp[k][i] = op;
					par[k][i] = j;
				} 
			}
		}
	}  
	cout<<dp[kk][n]<<endl; 	
	int x = par[kk][n];
	while(x > 0) {
		cout<<x + 1<< " ";
		x = par[--kk][x];
	}
}

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