Submission #101341

#	Time	Username	Problem	Language	Result	Execution time	Memory
101341		arman_ferdous	Split the sequence (APIO14_sequence)	C++17	50 / 100	2023 ms	32260 KiB

sequence

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

using ll = long long;
const int N = 10010;
const int K = 202;
const ll oo = 1e18;

int n, k;
ll a[N], S[N], dp[N][K], opt[N][K];

ll DP(int pos, int cnt) {
	if(pos <= 1) {
		if(cnt == k) return 0;
		return -oo;
	} if(cnt == k) return 0;
	if(dp[pos][cnt] != -1) return dp[pos][cnt];
	dp[pos][cnt] = -oo;
	for(int i = pos; i >= 1; i--) {
		ll A = S[i-1], B = S[pos] - S[i-1];
		ll got = A * B + DP(i-1, cnt+1);
		if(got > dp[pos][cnt]) {
			dp[pos][cnt] = got;
			opt[pos][cnt] = i;
		}
	} 
	return dp[pos][cnt];
}
int soln[N], ptr;
int main() {
	scanf("%d %d", &n, &k);
	for(int i = 1; i <= n; i++) {
		scanf("%lld", &a[i]);
		S[i] = S[i-1] + a[i];
	}
	memset(dp,-1,sizeof dp);
	printf("%lld\n", DP(n,0));

	int pos = n, cnt = 0;
	while(cnt != k) {
		soln[ptr++] = opt[pos][cnt] - 1;
		pos = opt[pos][cnt] - 1;
		cnt++;
	}
	for(int i = ptr-1; i >= 0; i--){
		printf("%d", soln[i]);
		if(i != 0) printf(" ");
	} puts("");
	return 0;
}

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:31: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:33: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: 0 / 21
• Subtask 6: 0 / 29