Submission #48027

#	Time	Username	Problem	Language	Result	Execution time	Memory
48027		E869120	Split the sequence (APIO14_sequence)	C++14	39 / 100	2069 ms	67836 KiB

sequence

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

long long N, K, A[100009], S;
pair<long long, long long>dp[10009][209];

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

	for (int i = 0; i <= N; i++) { for (int j = 0; j <= K; j++) dp[i][j] = make_pair((1LL << 60), -1); }

	dp[0][0] = make_pair(0, -1);
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= K; j++) {
			for (int k = 0; k < i; k++) {
				long long D = dp[k][j - 1].first + (A[i] - A[k])*(A[i] - A[k]); if (dp[i][j].first <= (A[i] - A[k])*(A[i] - A[k])) break;
				if (dp[i][j].first > D) {
					dp[i][j].first = D;
					dp[i][j].second = k;
				}
			}
		}
	}
	vector<int>C; int cx = N, cy = K;
	while (cx >= 1) {
		if (cx != N) C.push_back(cx);
		cx = dp[cx][cy].second; cy--;
	}
	reverse(C.begin(), C.end());
	cout << (S*S - dp[N][K].first) / 2 << endl;
	for (int i = 0; i < C.size(); i++) { if (i)cout << " "; cout << C[i]; }cout << endl;
	return 0;
}

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:35:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < C.size(); i++) { if (i)cout << " "; cout << C[i]; }cout << endl;
                  ~~^~~~~~~~~~

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