Submission #399000

#	Time	Username	Problem	Language	Result	Execution time	Memory
399000		wnguscjf01	Split the sequence (APIO14_sequence)	C++14	11 / 100	23 ms	10180 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(long long int a, long long int b, long long int c, long long int d){
	return 1.0*(d-b)/(a-c);
}
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++){
			if(sum[i] >= d[(j-1)%2][dsize[(j-1)%2]].s){ans[j%2][i] = d[(j-1)][dsize[(j-1)%2]].slope*sum[i] + d[(j-1)%2][dsize[(j-1)]].yy + sum[i]*sum[n] - sum[i]*sum[i]; tr[j][i] = d[(j-1)][dsize[(j-1)]].num;}
			else{
				struct data tmp;
				tmp.s = sum[i];
				int p = lower_bound(d[(j-1)%2], 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 = LLONG_MIN;
			else{
				while(cross(d[j%2][dsize[j%2]].slope,d[j%2][dsize[j%2]].yy,d[j%2][dsize[j%2]-1].slope,d[j%2][dsize[j%2]-1].yy) <= d[j%2][dsize[j%2]-1].s){
					d[j%2][dsize[j%2]-1].slope = d[j%2][dsize[j%2]].slope;
					d[j%2][dsize[j%2]-1].yy = d[j%2][dsize[j%2]].yy;
					d[j%2][dsize[j%2]-1].num = d[j%2][dsize[j%2]].num;
					dsize[j%2]--;
				}
				d[j%2][dsize[j%2]].s = cross(d[j%2][dsize[j%2]].slope,d[j%2][dsize[j%2]].yy,d[j%2][dsize[j%2]-1].slope,d[j%2][dsize[j%2]-1].yy);
			}
		}
		/*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
*/
/*
10 5
9 7 1 6 8 3 8 10 2 4
*/

Compilation message (stderr)

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

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