Submission #64284

#	Time	Username	Problem	Language	Result	Execution time	Memory
64284		kingpig9	Split the sequence (APIO14_sequence)	C++11	0 / 100	240 ms	132096 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 MAXK = 210;
const int MAXN = 1e5 + 10;

#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[MAXK][MAXN];	//minimum of sum of squares.
ll P[MAXN];

void rec (int id, 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]) + dp[id - 1][i];
		if (dp[id][mid] > val) {
			dp[id][mid] = val;
			oi = i;
		}
	}
	assert(oi != -1);
	rec(id, lt, mid - 1, olt, oi);
	rec(id, 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];
	}

	fillchar(dp, 63);
	dp[0][0] = 0;
	for (int i = 1; i <= K; i++) {
		rec(i, i, N, i - 1, N - 1);
	}
	printf("%lld\n", (sqr(P[N]) - dp[K][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