Submission #108682

#	Time	Username	Problem	Language	Result	Execution time	Memory
108682		autumn_eel	Split the sequence (APIO14_sequence)	C++14	50 / 100	2053 ms	99412 KiB

sequence

#include <bits/stdc++.h>
#define rep(i,n)for(int i=0;i<(n);i++)
using namespace std;
typedef long long ll;

ll dp[20000][300];
int prv[2000][300];

ll a[20000];

int main(){
	int n,K;cin>>n>>K;K++;
	ll cnt=0;
	rep(i,n){
		scanf("%lld",&a[i]);
		cnt+=a[i];
	}
	memset(dp,0x3f,sizeof(dp));
	dp[0][0]=0;
	rep(i,n)rep(j,K){
		ll sum=0;
		for(int k=i;k<n;k++){
			sum+=a[k];
			if(dp[k+1][j+1]>dp[i][j]+sum*sum){
				dp[k+1][j+1]=dp[i][j]+sum*sum;
				prv[k+1][j+1]=i;
			}
		}
	}
	ll res=(cnt*cnt-dp[n][K])/2;
	int x=n,y=K;
	vector<int>ans;
	while(1){
		x=prv[x][y];
		y--;
		if(!x)break;
		ans.push_back(x);
	}
	reverse(ans.begin(),ans.end());
	cout<<res<<endl;
	rep(i,ans.size()){
		if(i)printf(" ");
		printf("%d",ans[i]);
	}
	puts("");
}

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:2:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define rep(i,n)for(int i=0;i<(n);i++)
                              ^
sequence.cpp:41:2: note: in expansion of macro 'rep'
  rep(i,ans.size()){
  ^~~
sequence.cpp:15: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