Submission #173161

#	Time	Username	Problem	Language	Result	Execution time	Memory
173161		gs18081	Split the sequence (APIO14_sequence)	C++11	100 / 100	1383 ms	88568 KiB

sequence

#include <bits/stdc++.h>

using namespace std;

typedef long long int ll;
typedef pair<ll,ll> pl;

struct line{
	pl l;
	int idx;
	line(){}
	line(pl temp,int i){l = temp;idx = i;}
};


const int MAXN = 101010;
const int MAXK = 220;


int N,K;

ll DT[2][MAXN];
int from[MAXK][MAXN];
int arr[MAXN];
ll sum[MAXN];

ll calc(line l,ll p){
	return l.l.first * p + l.l.second;
}

double cross(line a,line b){
	return (double)(b.l.second - a.l.second) / (a.l.first - b.l.first);
}



int main(){
	scanf("%d %d",&N,&K);
	for(int i=1;i<=N;i++){
		scanf("%d",arr+i);
		sum[i] = sum[i-1] + arr[i];
	}
	for(int j=1;j<=K+1;j++){
		int now = 0;
		int p = (j+1) & 1;
		int n = j & 1;
		vector<line> hull;
		pl temp = pl(sum[j-1] , DT[p][j-1] - sum[j-1] * sum[N]);
		hull.push_back(line(temp,j-1));
		for(int i=j;i<=N;i++){
			while(now < hull.size() - 1 && cross(hull[now],hull[now+1]) <= sum[i]) now++;
			DT[n][i] = calc(hull[now],sum[i]) + sum[N] * sum[i] - sum[i] * sum[i];
			from[j][i] = hull[now].idx;
//			printf("%d %d %d %d %d\n",j,i,from[j][i],now,hull.size());
			pl temp = pl(sum[i] , DT[p][i] - sum[i] * sum[N]);
			line ttemp = line(temp,i);
			if(!hull.empty() && hull.back().l.first == temp.first && temp.second <= hull.back().l.second) continue;
			if(!hull.empty() && hull.back().l.first == temp.first) hull.pop_back(); 
			while(hull.size() > 1 && cross(hull.back() ,ttemp ) <= cross(hull[hull.size() - 2] , hull.back())) {
				hull.pop_back();
			}
			hull.push_back(line(temp,i));
			if(now >= hull.size()) now = hull.size() - 1;
		}
	}
	printf("%lld\n",DT[(K+1) & 1][N]);
	int now = N;
	int h = K+1;
	now = from[h][now];
	h--;
	vector<int> ans;
	while(h!=0){
		ans.push_back(now);
		assert(1<= now && now <= N-1);
		now = from[h][now];
		h--;
	}
	while(!ans.empty()){
		printf("%d ",ans.back());
		ans.pop_back();
	}
	printf("\n");


		
	return 0;

}

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:51:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    while(now < hull.size() - 1 && cross(hull[now],hull[now+1]) <= sum[i]) now++;
          ~~~~^~~~~~~~~~~~~~~~~
sequence.cpp:63:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if(now >= hull.size()) now = hull.size() - 1;
       ~~~~^~~~~~~~~~~~~~
sequence.cpp:38:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d",&N,&K);
  ~~~~~^~~~~~~~~~~~~~~
sequence.cpp:40:8: 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: 21 / 21
• Subtask 6: 29 / 29