Submission #89442

#	Time	Username	Problem	Language	Result	Execution time	Memory
89442		KLPP	Aliens (IOI16_aliens)	C++14	100 / 100	310 ms	42128 KiB

aliens

#include "aliens.h"
#include<algorithm>
#include<iostream>
#include<vector>
#include<stdio.h>
#include<queue>
#include<deque>
using namespace std;
#define INF 1000000000000000000
typedef pair<long long int,long long int> pii;
typedef long long int lld;
typedef pair<pii,int> line;
vector<pair<long long int,long long int> >arr;
//long long int DP[50001][4001];
int p;
lld Cost[1000000];
lld sq(lld x){
	return x*x;
}
lld sq2(lld x){
	if(x>0)return x*x;
	return 0;
}
void print(pii a){
	cout<<a.first<<" "<<a.second<<endl;
}
class CH{
	deque<line>d;
	public:
	double intersect(line a,line b){
		return (double)(b.first.second-a.first.second)/(a.first.first-b.first.first);
	}
	void Print(){
		/*queue<line> q;
		while(!d.empty()){
			print(d.front());
			q.push(d.front());
			d.pop_front();
		}
		while(!q.empty()){
			d.push_back(q.front());
			q.pop();
		}*/
	}
	void add(line A){//print(A);
		//cout<<d.size()<<endl;
		if(d.size()<2){
			d.push_back(A);
			return;
		}
		line B,C;
		do{
			B=d.back();
			d.pop_back();
			C=d.back();
		}while(d.size()>1 && intersect(A,B)<=intersect(B,C));
		if(intersect(A,B)>intersect(B,C)){
			d.push_back(B);
		}
		d.push_back(A);
	}
	int query(lld x){
		if(d.size()==1)return d.front().second;
		line A,B;
		do{
			A=d.front();
			d.pop_front();
			B=d.front();
		}while(d.size()>1 && intersect(A,B)<=x);
		if(intersect(A,B)>x)d.push_front(A);
		return d.front().second;
	}
};
lld Calc(lld M){
	lld DP[p];
	lld photo[p];
	DP[0]=0;
	photo[0]=0;
	CH *C=new CH();
	for(int i=1;i<=p;i++){//cout<<i<<endl;
		pii a=pii(-2*arr[i-1].first+2,sq(arr[i-1].first-1)-Cost[i-1]+DP[i-1]);
		line A=line(a,i-1);
		C->add(A);
		int j=C->query(arr[i-1].second);
		DP[i]=DP[j]-Cost[j]+sq(arr[i-1].second-arr[j].first+1)+M;
		photo[i]=photo[j]+1;
	}
	return DP[p]-photo[p]*M;
}
int Photos(lld M){
	lld DP[p];
	lld photo[p];
	DP[0]=0;
	photo[0]=0;
	CH *C=new CH();
	for(int i=1;i<=p;i++){//cout<<i<<endl;
		pii a=pii(-2*arr[i-1].first+2,sq(arr[i-1].first-1)-Cost[i-1]+DP[i-1]);
		line A=line(a,i-1);
		C->add(A);
		int j=C->query(arr[i-1].second);
		DP[i]=DP[j]-Cost[j]+sq(arr[i-1].second-arr[j].first+1)+M;
		photo[i]=photo[j]+1;
	}
	return photo[p];
}
long long take_photos(int n, int m, int k, vector<int> r,vector<int> c) {
 
	pair<long long int,long long int>points[n];
	for(int i=0;i<n;i++){
		points[i]=pair<long long int,long long int>(r[i],c[i]);
		if(r[i]>c[i])swap(points[i].first,points[i].second);
	}
	for(int i=0;i<n;i++)points[i].second=-points[i].second;
	sort(points,points+n);
	for(int i=0;i<n;i++)points[i].second=-points[i].second;
	long long int cnts=-1;
	lld cntf=-1;
	for(int i=0;i<n;i++){
		if(points[i].second>cnts && points[i].first>cntf){
			cnts=points[i].second;
			cntf=points[i].first;
			arr.push_back(points[i]);
			//print(points[i]);
		}
	}
	p=arr.size();
	for(int i=0;i<p;i++){
		if(i==0)Cost[i]=0;
		else{
			Cost[i]=sq2(-arr[i].first+arr[i-1].second+1);
		}//cout<<Cost[i]<<endl;
	}
	/*lld DP[p+1][k+1];
	for(int photo=0;photo<=k;photo++){
		for(int i=0;i<=p;i++){
			DP[i][photo]=INF;
		}
	}DP[0][0]=0;
	for(int photo=1;photo<=k;photo++){
		CH *C=new CH();
		DP[0][photo]=0;
		for(int i=1;i<=p;i++){
			if(DP[i-1][photo-1]<INF){
				pii a=pii(-2*arr[i-1].first+2,sq(arr[i-1].first-1)-Cost[i-1]+DP[i-1][photo-1]);
				line A=line(a,i-1);
				C->add(A);
			}
			DP[i][photo]=min(DP[i][photo],DP[i][photo-1]);
			int j=C->query(arr[i-1].second);
			DP[i][photo]=min(DP[i][photo],DP[j][photo-1]-Cost[j]+sq(arr[i-1].second-arr[j].first+1));
			
			//DP[i][photo]=min(DP[i][photo],sq(arr[i-1].second)+C->query(arr[i-1].second));
			//cout<<sq(arr[i-1].second)+C->query(arr[i-1].second)<<" "<<DP[i][photo]<<endl;
			//C->Print();
			//cout<<endl;
		}
	}*/
	lld lo=-1;
	lld hi=m+1;
	hi=hi*hi;
	lld DP[p+1];
	int photo[p+1];
	while(hi-lo>1){//cout<<hi<<" "<<lo<<endl;
		lld mid=(lo+hi)/2;
		if(Photos(mid)>k){
			lo=mid;
		}else hi=mid;
	}
	//cout<<lo<<" "<<hi<<endl;
	if(lo==-1){
		return Calc(0);
	}else{
		//cout<<Calc(lo)<<" "<<Calc(hi)<<endl;
		//cout<<Photos(lo)<<" "<<Photos(hi)<<endl;
		lld y1=Calc(lo);
		lld y2=Calc(hi);
		lld x1=Photos(lo);
		lld x2=Photos(hi);
		lld y=y1-y2;
		lld x=x1-x2;
		lld X=x1-k;
		lld ans=y1-(y*X)/x;
		return ans;
	}
	/*for(int photo=0;photo<=k;photo++){
		for(int i=0;i<=p;i++){
			cout<<DP[i][photo]<<" ";
		}cout<<endl;
	}*/
	/*CH *D=new CH();
	D->add(pii(2,1));
	D->add(pii(-2,1));
	D->add(pii(-3,2));D->Print();
	D->add(pii(-4,3));
	D->Print();*/
	
	return 0;
}

Compilation message (stderr)

aliens.cpp: In function 'long long int take_photos(int, int, int, std::vector<int>, std::vector<int>)':
aliens.cpp:161:6: warning: unused variable 'DP' [-Wunused-variable]
  lld DP[p+1];
      ^~
aliens.cpp:162:6: warning: unused variable 'photo' [-Wunused-variable]
  int photo[p+1];
      ^~~~~

• Subtask 1: 4 / 4
• Subtask 2: 12 / 12
• Subtask 3: 9 / 9
• Subtask 4: 16 / 16
• Subtask 5: 19 / 19
• Subtask 6: 40 / 40