Submission #76846

#	Time	Username	Problem	Language	Result	Execution time	Memory
76846		samuelfgs96	Split the sequence (APIO14_sequence)	C++11	100 / 100	1621 ms	83532 KiB

sequence

#include<bits/stdc++.h>

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back

using namespace std;

typedef pair<int, int> pii;
typedef long long ll;

const int N = 100002;
int n, k;
ll a[N], sum[N], dp[2][N];
ll cost (int l, int r) {
	return (sum[r+1] - sum[l]) * (sum[n] - sum[r+1]);
}
int nxt[210][N];
int prv, at;
void solve (int lo, int hi, int opt_beg, int opt_end, int k) {
	if (lo > hi) return ;
	int mid = (lo + hi) / 2;
	int opt = -1;
	dp[at][mid] = -1;
	for (int i = max(mid, opt_beg); i <= opt_end; i++) {
		ll tmp = dp[prv][i+1] + cost(mid, i);
		if (dp[at][mid] < tmp) {
			dp[at][mid] = tmp;
			opt = i;
		}
	}
	nxt[k][mid] = opt;
	solve(lo, mid-1, opt_beg, opt, k);
	solve(mid+1, hi, opt, opt_end, k);
}
int main (void) {
	scanf("%d %d", &n, &k);
	for (int i = 0; i < n; i++) {
		scanf("%lld", a + i);
		sum[i+1] = sum[i] + a[i];
	}

	memset (dp, -1, sizeof dp);
	for (int i = 0; i < n; i++) dp[0][i] = 0;
	at = 1;
	for (int i = 1; i <= k; i++) {
		solve(0, n-1, 0, n-1, i);
		swap (prv, at);
	}
	cout << dp[prv][0] << endl;
	vector <int> path;
	int x = k, y = 0;
	while (x) {
		path.pb(nxt[x][y]);
		y = nxt[x][y] + 1;
		x--;
	}
	for (auto u : path) cout << u + 1 << " ";
	cout << endl;
	return 0;
}

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:39: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:41:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld", a + 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