Submission #537221

#	Time	Username	Problem	Language	Result	Execution time	Memory
537221		LucaDantas	Split the sequence (APIO14_sequence)	C++17	0 / 100	140 ms	131072 KiB

sequence

#include <bits/stdc++.h>
using namespace std;

constexpr int maxn = 1e5+10, maxk = 210;

int a[maxn], suf[maxn];

int itv(int l, int r) { return suf[l] - suf[r+1]; }

long long dp[maxn][maxk];
int opt[maxn][maxk];

void solve(int l, int r, int l2, int r2, int k) {
	if(l > r) return;
	int m = (l+r) >> 1;
	
	pair<long long, int> ans;
	for(int i = min(m-1, r2); i >= l2; i--)
		ans = max(ans, {dp[i][k-1] + 1ll * suf[m+1] * itv(i+1, m), i});

	opt[m][k] = ans.second;
	dp[m][k] = ans.first;

	solve(l, m-1, l2, ans.second, k);
	solve(m+1, r, ans.second, r2, k);
}

int main() {
	int n, k; scanf("%d %d", &n, &k);
	for(int i = 1; i <= n; i++)
		scanf("%d", a+i);
	for(int i = n; i >= 1; i--)
		suf[i] = suf[i+1] + a[i];
	for(int i = 1; i <= k; i++)
		solve(1, n-1, 0, n-1, i);
	pair<long long, int> best;
	vector<int> ans;
	for(int i = 1; i <= n; i++)
		best = max(best, {dp[i][k], i});
	int i = best.second;
	while(i)
		ans.push_back(i), i = opt[i][k], --k;
	printf("%lld\n", best.first);
	reverse(ans.begin(), ans.end());
	for(int x : ans)
		printf("%d ", x);
	puts("");
}

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:29:17: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   29 |  int n, k; scanf("%d %d", &n, &k);
      |            ~~~~~^~~~~~~~~~~~~~~~~
sequence.cpp:31:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   31 |   scanf("%d", a+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