Submission #64758

#	Time	Username	Problem	Language	Result	Execution time	Memory
64758		leejseo	Split the sequence (APIO14_sequence)	C++11	0 / 100	2029 ms	132096 KiB

sequence

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
typedef long long lld;
const static int MAXN = 100005;
const static int MAXK = 205;
int N, K, P[MAXN][MAXK];
lld S[MAXN], D[MAXN][MAXK];

void input(){
	cin >> N >> K;
	for (int i=1; i<=N; i++){
		cin >> S[i];
		S[i] += S[i-1];
	}
}

int DP(){
	memset(D, -1, sizeof(D));
	for (int i=1; i<=N; i++) D[i][0] = 0;
	for (int i=1; i<=N; i++){
		for (int j=1; j<=min(K, i-1); j++){
			int prev = -1;
			for (int k=1; k<i; k++){
				if (D[k][j-1] == -1) continue;
				lld val = D[k][j-1] + S[k] * (S[i] - S[k]);
				if (val > D[i][j]){
					prev = k;
					D[i][j] = val;
				}
			}
			P[i][j] = prev;		
		}
	}
	return K;
}

int main(){
	ios::sync_with_stdio(false); cin.tie(NULL);
	input();
	int j = DP();
	cout << D[N][j] << endl;
	vector<int> ans;
	int i = N;
	while (j > 0){
		ans.push_back(P[i][j]);
		i = P[i][j];
		j -= 1;
	}
	reverse(ans.begin(), ans.end());
	for (auto &i : ans) cout << i << ' ';
	cout << endl;
}

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