Submission #64289

#	Time	Username	Problem	Language	Result	Execution time	Memory
64289		kingpig9	Split the sequence (APIO14_sequence)	C++11	100 / 100	1637 ms	83784 KiB

sequence

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAXN = 1e5 + 10, MAXK = 210;
const ll INF = LLONG_MAX / 3;

#define debug(...) fprintf(stderr, __VA_ARGS__)
#define fi first
#define se second
#define all(v) (v).begin(), (v).end()
#define fillchar(a, s) memset((a), (s), sizeof(a))

inline ll sqr (ll x) {
	return x * x;
}

int N, K;
ll P[MAXN];
ll dp[2][MAXN];	//minimum of sum of squares.
int opt[MAXK][MAXN];
int ci;
ll *cdp, *pdp;

void rec (int lt, int rt, int olt, int ort) {
	if (lt > rt) {
		return;
	}
	int mid = (lt + rt) / 2;
	int oi = -1;
	for (int i = olt; i <= ort && i < mid; i++) {
		ll val = sqr(P[mid] - P[i]) + pdp[i];
		if (cdp[mid] > val) {
			cdp[mid] = val;
			oi = i;
		}
	}
	opt[ci][mid] = oi;
	assert(oi != -1);
	rec(lt, mid - 1, olt, oi);
	rec(mid + 1, rt, oi, ort);
}

int main() {
	scanf("%d %d", &N, &K);
	K++;
	for (int i = 1; i <= N; i++) {
		scanf("%lld", &P[i]);
		P[i] += P[i - 1];
	}

	for (int i = 0; i < 2; i++) {
		for (int j = 0; j <= N; j++) {
			dp[i][j] = INF;
		}
	}

	cdp = dp[0];
	pdp = dp[1];
	cdp[0] = 0;

	for (int i = 1; i <= K; i++) {
		swap(cdp, pdp);
		for (int j = 0; j <= N; j++) {
			cdp[j] = INF;
		}
		ci = i;
		rec(i, N, i - 1, N - 1);
	}
	printf("%lld\n", (sqr(P[N]) - cdp[N]) / 2);
	int oi = N;
	for (int i = K; i > 1; i--) {
		oi = opt[i][oi];
		printf("%d ", oi);
	}
	puts("");
}

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:48:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &N, &K);
  ~~~~~^~~~~~~~~~~~~~~~~
sequence.cpp:51:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld", &P[i]);
   ~~~~~^~~~~~~~~~~~~~~

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