Submission #244095

#	Time	Username	Problem	Language	Result	Execution time	Memory
244095		nandonathaniel	Split the sequence (APIO14_sequence)	C++14	100 / 100	1341 ms	81076 KiB

sequence

#include<bits/stdc++.h>
using namespace std;
const int MAXN=100005,MAXK=205;

long long dp[2][MAXN],pref[MAXN];  //max cost dari 1...i dibagi j bagian
int opt[MAXK][MAXN],n;

long long cost(int x,int y){
	return (pref[x-1])*(pref[y]-pref[x-1]);
}

void dnc(int L,int R,int optL,int optR,int j){
	if(L>R)return;
	int mid=(L+R)/2,idx=0;
	long long res=-1e18;
	for(int i=optL;i<=min(optR,mid-1);i++){
		if(dp[(j-1)&1][i]+cost(i+1,mid)>res){
			res=dp[(j-1)&1][i]+cost(i+1,mid);
			idx=i;
		}
	}
	dp[j&1][mid]=res;
	opt[j][mid]=idx;
	dnc(L,mid-1,optL,opt[j][mid],j);
	dnc(mid+1,R,opt[j][mid],optR,j);
}

int main(){
	ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
	int k,a;
	cin >> n >> k;
	k++;
	for(int i=1;i<=n;i++){
		cin >> a;
		pref[i]=pref[i-1]+a;
	}
	for(int i=2;i<=k;i++)dnc(i,n,i-1,n-1,i);
	cout << dp[k&1][n] << '\n';
	vector<int> id;
	int j=n;
	for(int i=k;i>=2;i--){
		j=opt[i][j];
		id.push_back(j);
	}
	reverse(id.begin(),id.end());
	for(int i=0;i<id.size();i++){
		if(i<id.size()-1)cout << id[i] << " ";
		else cout << id[i] << '\n';
	}
	return 0;
}

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:46:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<id.size();i++){
              ~^~~~~~~~~~
sequence.cpp:47:7: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(i<id.size()-1)cout << id[i] << " ";
      ~^~~~~~~~~~~~

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