Submission #67473

#	Time	Username	Problem	Language	Result	Execution time	Memory
67473		KLPP	Split the sequence (APIO14_sequence)	C++14	11 / 100	53 ms	8428 KiB

sequence

#include<stdio.h>
#include<iostream>
#include<queue>
using namespace std;
typedef long long int lld;
typedef pair<lld,lld> line;
#define INF 1000000000000000000
lld sq(lld x){
  	return x*x;
}
bool irrelevant(line a, line b, line c){
	lld Y=c.second*a.first-a.second*c.first;
	lld X=b.first*(c.second-a.second)+b.second*(a.first-c.first);
	if(Y<X)return true;
	return false;
}
lld val(line a, lld b){
	return a.first*b+a.second;
}
class CH{
	private:
	deque<pair<line,int> >d;
	
	public:
		bool empty(){
			return d.empty();
		}
		void add(line a, int i){
			bool trabalha=true;
			while(d.size()>=3 && trabalha){
				pair<line,int> b=d.back();
				d.pop_back();
				pair<line,int> c=d.back();
				if(!irrelevant(a,b.first,c.first)){
					trabalha=false;
					d.push_back(b);
				}
			}
			pair<line,int>A=pair<line,int>(a,i);
			d.push_back(A); 
		}
		int query(lld x){
			bool trabalha=true;
			while(d.size()>=2 && trabalha){
				pair<line,int> a,b;
				a=d.front();
				d.pop_front();
				b=d.front();
				if(val(a.first,x)<val(b.first,x)){
					d.push_front(a);
					trabalha=false;
				}
			}
			return d.front().second;
		}

};
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;
    		for(int j=1;j<=n;j++){
    			if(DP[j-1][parts]!=INF)A.add(pair<lld,lld>(-2*acc[j-1],DP[j-1][parts]+sq(acc[j-1])),j-1);
			if(!A.empty()){
				int i=A.query(acc[j]);
    				DP[j][parts+1]=DP[i][parts]+sq(acc[j]-acc[i]);
    				prev[j][parts+1]=i;
    			}
    		}
    	}
    	/*for(int parts=0;parts<=k+1;parts++){
    		for(int i=0;i<=n;i++){
    			printf("%d ",prev[i][parts]);
    		}printf("\n");
    	}*/
    	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");
     
    	return 0;
}

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:60:11: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
      scanf("%d %d",&n,&k);
      ~~~~~^~~~~~~~~~~~~~~
sequence.cpp:63:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf("%lld",&arr[i]);
       ~~~~~^~~~~~~~~~~~~~~~

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