Submission #33961

#	Time	Username	Problem	Language	Result	Execution time	Memory
33961		mohammad_kilani	Split the sequence (APIO14_sequence)	C++14	50 / 100	493 ms	3608 KiB

sequence

#include <bits/stdc++.h>
using namespace std;
#define mod 1000000007
#define oo 2000000000
const int N = 1010 , K = 201;
int n , k , arr[N] , sum[N];
long long dp[N][K];

long long solve(int i,int j){
	if(j == k) return 0;
	if(i == n) return -4e18;
	if(dp[i][j] != -1) return dp[i][j];
	dp[i][j] = 0 ;
	for(int l=i;l<n;l++){
		long long cur = sum[l+1] - sum[i];
		long long cur2 = sum[n] - sum[l+1];
		long long num = cur * cur2;
		dp[i][j] = max(dp[i][j],num + solve(l+1,j+1));
	}
	return dp[i][j];
}

void buildpath(int i,int j){
	if(j == k) return;
	if(i == n) return;
	for(int l=i;l<n;l++){
		long long cur1 = sum[l+1] - sum[i];
		long long cur2 = sum[n] - sum[l+1];
		long long num = cur1 * cur2;
		if(num + solve(l+1,j+1) == dp[i][j]){
			printf("%d ",l+1);
			buildpath(l+1,j+1);
			return ;
		}
	}
}


int main() {
	//freopen("in.txt","r",stdin);
	scanf("%d%d",&n,&k);
	for(int i=0;i<n;i++){
		scanf("%d",&arr[i]);
		sum[i+1] = sum[i] + arr[i];
	}
	memset(dp,-1,sizeof(dp));
	cout << solve(0,0) << endl;
	buildpath(0,0);
	cout << endl;
	return 0;
}

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:41:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d",&n,&k);
                     ^
sequence.cpp:43:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&arr[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