Submission #25171

#	Time	Username	Problem	Language	Result	Execution time	Memory
25171		RezwanArefin01	Split the sequence (APIO14_sequence)	C++14	50 / 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];

void recon(int k, int n) {
	if(!k) return; 
	recon(k-1, par[k][n]); 
	cout<<par[k][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];
	} 
	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; 	
	recon(kk, n);
}

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