Submission #399009

#	Time	Username	Problem	Language	Result	Execution time	Memory
399009		wnguscjf01	Split the sequence (APIO14_sequence)	C++14	100 / 100	1595 ms	87628 KiB

sequence

#include<bits/stdc++.h>
#define MAXK 201
#define MAXN 100001
using namespace std;
struct data{
	long long int slope, yy;
	double s;
	int num;
};
struct data d[2][MAXN];
bool compare(const struct data &a, const struct data &b){
	return a.s < b.s;
}
double cross(struct data &a, struct data &b){
	if(a.slope == b.slope) return -1.0*LLONG_MIN;
	return 1.0*(b.yy-a.yy)/(a.slope-b.slope);
}
long long int ans[2][MAXN], sum[MAXN];
int dsize[2], tr[MAXK][MAXN], ans2[MAXN];
int main()
{
	int n, k, i, j;
	cin >> n >> k;
	
	for(i=1; i<=n; i++){
		int aa;
		scanf("%d",&aa);
		sum[i] = sum[i-1]+aa;
	}
	
	for(j=1; j<=k; j++){
		dsize[j%2]=0;
		for(i=j; i<n; i++){
			struct data tmp;
			tmp.s = sum[i];
			int p = lower_bound(d[(j-1)%2]+1, d[(j-1)%2]+dsize[(j-1)%2]+1,tmp,compare)-d[(j-1)%2]-1;
			ans[j%2][i] = d[(j-1)%2][p].slope*sum[i] + d[(j-1)%2][p].yy + sum[i]*sum[n] - sum[i]*sum[i];
			tr[j][i] = d[(j-1)%2][p].num;
			
			dsize[j%2]++;
			d[j%2][dsize[j%2]].slope = sum[i];
			d[j%2][dsize[j%2]].yy = ans[j%2][i] - sum[i]*sum[n];
			d[j%2][dsize[j%2]].num = i;
			if(dsize[j%2]==1) d[j%2][dsize[j%2]].s = INT_MIN;
			else{
				while(dsize[j%2] > 1 && cross(d[j%2][dsize[j%2]],d[j%2][dsize[j%2]-1]) <= d[j%2][dsize[j%2]-1].s){
					d[j%2][dsize[j%2]-1] = d[j%2][dsize[j%2]];
					dsize[j%2]--;
				}
				d[j%2][dsize[j%2]].s = cross(d[j%2][dsize[j%2]],d[j%2][dsize[j%2]-1]);
			}
		}
		/*for(i=1; i<n; i++){
			printf("%lld  ",ans[j%2][i]);
		}
		cout << endl;*/
	}
	
	int maxind = 1;
	for(i=k; i<n; i++){
		if(ans[k%2][i] > ans[k%2][maxind]) maxind = i;
	}
	printf("%lld\n",ans[k%2][maxind]);
	int p = k, q = maxind;
	while(1){
		if(p<1) break;
		ans2[p] = q;
		q = tr[p][q];
		p--;
	}
	for(i=1; i<=k; i++) printf("%d ",ans2[i]);
	
	return 0;
}
/*
7 3
4 1 3 4 0 2 3
*/
/*
5 4
8 9 6 2 5
*/
/*
17 5
9 7 0 0 0 1 6 0 0 8 3 0 8 10 2 0 4
*/
/*
10 5
9 7 1 6 8 3 8 10 2 4
*/

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:27:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   27 |   scanf("%d",&aa);
      |   ~~~~~^~~~~~~~~~

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