Submission #64288

#	Time	Username	Problem	Language	Result	Execution time	Memory
64288		kingpig9	Split the sequence (APIO14_sequence)	C++11	0 / 100	38 ms	2872 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;
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 dp[2][MAXN];	//minimum of sum of squares.
ll P[MAXN];

void rec (ll *cdp, ll *pdp, 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;
		}
	}
	assert(oi != -1);
	rec(cdp, pdp, lt, mid - 1, olt, oi);
	rec(cdp, pdp, 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;
		}
	}

	int cur = 0, prv = 1;
	dp[cur][0] = 0;

	for (int i = 1; i <= K; i++) {
		swap(cur, prv);
		for (int j = 0; j <= N; j++) {
			dp[cur][j] = INF;
		}
		rec(dp[cur], dp[prv], i, N, i - 1, N - 1);
	}
	printf("%lld\n", (sqr(P[N]) - dp[cur][N]) / 2);
}

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:44: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:47:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld", &P[i]);
   ~~~~~^~~~~~~~~~~~~~~

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