Submission #36431

#	Time	Username	Problem	Language	Result	Execution time	Memory
36431		ToMoClone	Split the sequence (APIO14_sequence)	C++14	0 / 100	26 ms	3884 KiB

sequence

/*input
7 3
4 1 3 4 0 2 3
*/
#include <vector>
#include <stdio.h>
using namespace std;

vector<long long> ans, val;
int n, k, sum[100005];

void solve(int l, int r, int u, int v){
	int mid = (l + r) >> 1, pos = 0;

	ans[mid] = 0;
	for(int i = u; i <= min(mid, 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], pos = i;

	if(l == r) return;
	solve(l, mid, u, pos);
	solve(mid + 1, r, pos, v);
}

int main(){
	scanf("%d%d", &n, &k);
	for(int i = 1; i <= n; ++i)
		scanf("%d", &sum[i]), sum[i] += sum[i - 1];
	ans.resize(n + 1), val.resize(n + 1);

	for(int i = 1; i <= k; ++i)
		ans.swap(val), solve(1, n, 1, n);
	printf("%lld\n", ans[n]);
}

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:26: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:28:45: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &sum[i]), sum[i] += sum[i - 1];
                                             ^

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