Submission #13642

#	Time	Username	Problem	Language	Result	Execution time	Memory
13642		tncks0121	Split the sequence (APIO14_sequence)	C++14	0 / 100	0 ms	84560 KiB

sequence

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <algorithm>
#include <string>
#include <functional>
#include <vector>
#include <numeric>
#include <deque>
#include <utility>
#include <bitset>
#include <limits.h>
#include <iostream>
#include <unordered_map>

using namespace std;
typedef long long ll;
typedef unsigned long long llu;
typedef double lf;
typedef unsigned int uint;
typedef long double llf;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int N_ = 100500;
const int K_ = 205;
int N, K; ll S[N_];

ll table[2][N_];
int rev[K_][N_];

ll sq(ll a) { return a * a; }

deque<int> deq;

int main() {

	scanf("%d%d", &N, &K); ++K;
	for (int i = 1; i <= N; i++) {
		int x; scanf("%d", &x);
		S[i] = S[i - 1] + x;
	}
	
	// min sum {s^2}
	for (int i = 1; i <= N; i++) table[1][i] = sq(S[i]);
	for (int k = 2; k <= K; k++) {
		ll *cur = table[k & 1];
		ll *prv = table[~k & 1];
		for (int i = 1; i <= N; i++) cur[i] = prv[i];

		cur[k] = prv[k - 1] + sq(S[k] - S[k - 1]);
		rev[k][k] = k - 1;
		deq.push_back(k - 1);

		for (int i = k + 1; i <= N; i++) {
			// get best
			{
				while (deq.size() > 1) {
					int a = deq[0], b = deq[1];
					lf ix = (lf)(prv[b] - prv[a] + sq(S[b]) - sq(S[a])) / (2 * S[b] - 2 * S[a]);
					if (S[i] <= ix) break;
					deq.pop_front();
				}
			}

			// insert line
			{
				while (deq.size() > 1) {
					int t = *deq.rbegin();
					if (S[t] == S[i]) break;
					int l = *++deq.rbegin();

					lf i1 = (lf)(prv[l] - prv[t] + sq(S[l]) - sq(S[t])) / (2 * S[l] - 2 * S[t]);
					lf i2 = (lf)(prv[i - 1] - prv[t] + sq(S[i - 1]) - sq(S[t])) / (2 * S[i - 1] - 2 * S[t]);

					if (i1 > i2) deq.pop_back();
					else break;
				}
				deq.push_back(i - 1);
			}

			// update
			{
				int j = deq.front();
				cur[i] = (prv[j] + sq(S[j])) - 2 * S[j] * S[i] + sq(S[i]);
				rev[k][i] = j;
			}

		}
	}
	
	/*for (int k = 2; k <= K; k++) {
		for (int i = k; i <= N; i++) {
			// naive
			printf("tb[%d,%d] = %lld -> ", k,i,table[k][i]);
			table[k][i] = table[k - 1][i];
			for (int j = k - 1; j < i; j++) {
				ll cur = (table[k - 1][j] + sq(S[j])) - 2 * S[j] * S[i] + sq(S[i]);
						// ----------------constant  -----기울기  ---x좌표  --------상관X
				table[k][i] = min(table[k][i], cur);
			}
			printf("%lld\n", table[k][i]);
		}
	}*/

	printf("%lld\n", (sq(S[N]) - table[K & 1][N]) / 2);
	
	vector<int> rec;
	for (int i = K, j = N; i > 0;) {
		if(i < K) rec.push_back(j);
		j = rev[i--][j];
	}

	reverse(rec.begin(), rec.end());
	for (int x : rec) printf("%d ", x);

	return 0;
}

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