Submission #43642

#	Time	Username	Problem	Language	Result	Execution time	Memory
43642		sorry_Benq	Split the sequence (APIO14_sequence)	C++14	50 / 100	2040 ms	16748 KiB

sequence

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

ll S[10005];
ll DP[10005][205];
const ll INF = 1e18;

int main(){
	S[0] = 0;
	int N, K; cin >> N >> K;
	for (int i = 1; i <= N; i++){
		ll x; cin >> x;
		S[i] = S[i - 1] + x;
	}
	for (int i = 1; i <= N; i++){
		DP[i][1] = S[i]*S[i];
	}
	for (int j = 2; j <= K + 1; j++){
		for (int i = j; i <= N; i++){
			DP[i][j] = INF;
			for (int r = j - 1; r < i; r++){
				DP[i][j] = min(DP[i][j], (S[i] - S[r]) * (S[i] - S[r]) + DP[r][j - 1]);
			}
		}
	}
	int curpos = N;
	vector<int> idx; 
	for (int j = K + 1; j >= 2; j--){
		for (int i = curpos - 1; i >= 0; i--){
			if (DP[curpos][j] == DP[i][j - 1] + (S[i] - S[curpos])*(S[i] - S[curpos])){
				idx.push_back(i);
				curpos = i;
				break;
			}
		}
	}
	sort(idx.begin(), idx.end());
	cout << (S[N] * S[N] - DP[N][K + 1])/2 << endl;
	for (int j: idx){
		cout << j << ' ';
	}
	cout << endl;
}

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