Submission #59667

#	Time	Username	Problem	Language	Result	Execution time	Memory
59667		KLPP	Split the sequence (APIO14_sequence)	C++14	0 / 100	123 ms	12248 KiB

sequence

#include<stdio.h>
#include<iostream>
#include<vector>
using namespace std;
typedef long long int lld;
#define INF 1000000000000000000
typedef pair<lld,lld> pii;
lld sq(lld x){
	return x*x;
}
bool cmp(pii l1, pii l2, pii l3){
	lld a=l3.first-l2.first;
	lld b=l2.second-l3.second;
	lld c=l2.first-l1.first;
	lld d=l1.second-l2.second;
	if(a*d>b*c)return true;
	return false;
}
class CH{
	vector<pii> points;
	vector<pii>lines;
	vector<int> index;
	public:
		void add(pii line,int indice){
			while(lines.size()>1 && cmp(lines[lines.size()-2],lines[lines.size()-1],line)){
				lines.pop_back();
				points.pop_back();
				index.pop_back();
			}
			if(lines.size()>0){
				pii a=pii(line.second-lines[lines.size()-1].second,-line.first+lines[lines.size()-1].first);
				points.push_back(a);
			}
			lines.push_back(line);
			index.push_back(indice);
		}
		int query(lld x){
			//cout<<points.size()<<endl;
			if(lines.size()==0)return -1;
			int lo,hi;
			lo=-1;
			hi=points.size();//cout<<lo<<hi<<endl;
			while(hi-lo>1){
				int mid=(hi+lo)/2;
				if(points[mid].first<x*points[mid].second){//cout<<mid<<endl;
					lo=mid;
				}else hi=mid;
			}//cout<<lo<<hi<<endl;
			//for(int i=0;i<points.size();i++)cout<<points[i].first<<" "<<points[i].second<<endl;
			return index[hi];
		}
		int size(){
			return lines.size();
		}
		void print(){
			for(int i=0;i<index.size();i++)cout<<index[i]<<" ";
			cout<<endl;
		}
};
int main(){
	int n,k;
	scanf("%d %d",&n,&k);
	lld arr[n];
	for(int i=0;i<n;i++){
		scanf("%lld",&arr[i]);
	}
	lld DP[n+1][k+2];
	int prev[n+1][k+2];
	lld acc[n+1];
	acc[0]=0;
	for(int i=0;i<n;i++){
		acc[i+1]=acc[i]+arr[i];
	}
	for(int i=0;i<=n;i++){
		for(int j=0;j<=k+1;j++){
			DP[i][j]=INF;
			prev[i][j]=-1;
		}
	}
	DP[0][0]=0;
	for(int parts=0;parts<=k;parts++){
		CH a;//cout<<"A"<<endl;
		for(int j=0;j<=n;j++){
			prev[j][parts+1]=a.query(acc[j]);
			if(DP[j][parts]!=INF){
				a.add(pii(-2*acc[j],acc[j]*acc[j]+DP[j][parts]),j);
			}
			if(prev[j][parts+1]!=-1){
				int i=prev[j][parts+1];
				DP[j][parts+1]=DP[i][parts]+sq(acc[j]-acc[i]);
			}
			//cout<<a.query(acc[j])<<" "<<a.size()<<" ";
			//a.print();
		}//cout<<endl;
	}
	/*for(int i=0;i<k+2;i++){
		for(int j=0;j<=n;j++){
			if(DP[j][i]==INF)cout<<"-1 ";
			else cout<<DP[j][i]<<" ";
		}cout<<endl;
	}
	for(int i=0;i<k+2;i++){
		for(int j=0;j<=n;j++){
			cout<<prev[j][i]<<" ";
		}cout<<endl;
	}*/
	lld ans=sq(acc[n])-DP[n][k+1];
	ans/=2;
	printf("%lld\n",ans);
	int index=n;
	int partition=k+1;
	while(index>0){
		index=prev[index][partition];
		partition--;
		if(index>0)printf("%d ",index);
	}
	printf("\n");

	/*int m;
	cin>>m;
	CH a;
	pii arr[m];
	for(int i=0;i<m;i++){
		int x,y;
		cin>>x>>y;
		if(x==-1){
			cout<<a.query(y)<<endl;
		}else{
			a.add(pii(x,y),i);
			arr[i]=pii(x,y);
		}
	}*/
	return 0;
}

Compilation message (stderr)

sequence.cpp: In member function 'void CH::print()':
sequence.cpp:56:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int i=0;i<index.size();i++)cout<<index[i]<<" ";
                ~^~~~~~~~~~~~~
sequence.cpp: In function 'int main()':
sequence.cpp:62: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:65:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld",&arr[i]);
   ~~~~~^~~~~~~~~~~~~~~~

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