Submission #36448

#	Time	Username	Problem	Language	Result	Execution time	Memory
36448		ToMoClone	Split the sequence (APIO14_sequence)	C++14	100 / 100	1813 ms	82796 KiB

sequence

/*input
7 3
4 1 3 4 0 2 3
*/
#include <vector>
#include <stdio.h>
#include <algorithm>
using namespace std;
 
vector<long long> ans, val, sum;
int n, k, trace[201][100001];
 
void solve(int step, int l, int r, int u, int v){
	int mid = (l + r) >> 1;
 
	ans[mid] = 0;
	for(int i = u; i <= min(mid - 1, v); ++i)
		if(ans[mid] <= 1ll * sum[i] * (sum[mid] - sum[i]) + val[i])
			ans[mid] = 1ll * sum[i] * (sum[mid] - sum[i]) + val[i], trace[step][mid] = i;
 
	if(l == r) return;
	solve(step, l, mid, u, trace[step][mid]);
	solve(step, mid + 1, r, trace[step][mid], v);
}
 
int main(){
	scanf("%d%d", &n, &k);
	sum.resize(n + 1), ans.resize(n + 1), val.resize(n + 1);
	for(int i = 1; i <= n; ++i)
		scanf("%lld", &sum[i]), sum[i] += sum[i - 1];
 
	for(int i = 1; i <= k; ++i)
		ans.swap(val), solve(i, 1, n, 1, n - 1);
	
	printf("%lld\n", ans[n]);
 
	vector<int> res;
	while(k != 0 && n != 0) res.push_back(trace[k][n]), n = trace[k--][n];
	reverse(res.begin(), res.end());
	for(int i = 0; i < (int)res.size(); ++i)
		printf("%s%d", i ? " " : "", res[i]);
}

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:27:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &n, &k);
                       ^
sequence.cpp:30:47: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld", &sum[i]), sum[i] += sum[i - 1];
                                               ^

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