Submission #36433

#	Time	Username	Problem	Language	Result	Execution time	Memory
36433		ToMoClone	Split the sequence (APIO14_sequence)	C++14	0 / 100	0 ms	1928 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, sum;
int n, k;

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(){
	freopen("sequence.in", "r", stdin);
	freopen("sequence.out", "w", stdout);
	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(1, n, 1, n);
	printf("%lld\n", ans[n]);
}

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:26:36: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  freopen("sequence.in", "r", stdin);
                                    ^
sequence.cpp:27:38: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  freopen("sequence.out", "w", stdout);
                                      ^
sequence.cpp:28: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:31: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: 0 / 11
• Subtask 2: 0 / 11
• Subtask 3: 0 / 11
• Subtask 4: 0 / 17
• Subtask 5: 0 / 21
• Subtask 6: 0 / 29