Submission #74107

#	Time	Username	Problem	Language	Result	Execution time	Memory
74107		KLPP	Aliens (IOI16_aliens)	C++14	4 / 100	3 ms	976 KiB

aliens

#include "aliens.h"
#include<algorithm>
#include<iostream>
#include<vector>
#include<stdio.h>
#include<queue>
using namespace std;
#define INF 1000000000000000000
typedef pair<long long int,long long int> pii;
typedef long long int lld;
vector<pair<long long int,long long int> >arr;
long long int DP[50001][4001];
int p;
lld sq(lld x){
	return x*x;
}
long long sq2(long long x){
	if(x>0)return x*x;
	return 0;
}
bool cmp(pii a, pii b){
	if(a.first==b.first){
		if(a.second>b.second)return true;
		return false;
	}
	if(a.first<b.first)return true;
	return false;
}
long long int min(long long int a, long long int b){
	if(a<b)return a;
	return b;
}
lld val(pii a, lld x){
	return a.first*x+a.second;
}
bool useless(pii a, pii b, pii c){
	if(c.first*a.second-c.second*a.first<=b.first*c.second-a.second*b.first+a.first*b.second-c.first*b.second)return true;
	return false;
}
class CH{
	deque<pii> d;
	public:
	void add(pii p){
		if(d.size()<2){
			d.push_back(p);return;
		}
		pii a,b;
		bool B=true;
		do{
			a=d.back();d.pop_back();
			b=d.back();
			if(useless(b,a,p)){
				
			}else{
				B=false;
				d.push_back(a);
			}
		}while(B && d.size()>=2);
		d.push_back(p);
	}
	lld query(lld x){
		lld ans=val(d.front(),x);
		bool b=true;
		while(b && d.size()>=2){
			pii a=d.front();d.pop_front();
			if(ans>val(d.front(),x)){
				ans=val(d.front(),x);
			}else{
				b=false;
				d.push_front(a);
			}
		}
		return ans;
	}
	void clear(){
		d.clear();
	}
	void size(){
		cout<<d.size()<<endl;
	}
	void front(){
		cout<<d.front().first<<" "<<d.front().second<<endl;
	}
};
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);
	}
	sort(points,points+n,cmp);
	long long int cnt=-1;
	for(int i=0;i<n;i++){
		if(points[i].second>cnt){
			cnt=points[i].second;
			arr.push_back(points[i]);
		}
	}
	p=arr.size();
	for(int i=0;i<=k;i++){
		for(int j=0;j<=p;j++){
			DP[j][i]=INF;
		}
	}
	lld penalty[p];
	for(int i=1;i<p;i++){
		penalty[i]=-sq2(arr[i-1].second-arr[i].first+1);
		//cout<<penalty[i]<<endl;
	}penalty[0]=0;
	DP[0][0]=0;
	long long int ans=INF;
	CH *A;
	A=new CH();
	//A->add(pii(2*(-arr[0].first+1),sq(arr[0].first-1)));
	//A->size();
	for(int photo=1;photo<=k;photo++){
		for(int i=0;i<p;i++){//A->front();
			A->add(pii(2*(-arr[i].first+1),sq(-arr[i].first+1)+DP[i][photo-1]+penalty[i]));
			if(i+1>=photo)DP[i+1][photo]=min(A->query(arr[i].second)+arr[i].second*arr[i].second,DP[i+1][photo]);
			//A->front();
			//cout<<arr[i].first<<" "<<arr[i].second<<" "<<A->query(arr[i].second)<<endl;
		}//cout<<endl;
		A->clear();
		/*for(int i=0;i<=p;i++){
			cout<<DP[i][photo]<<" "<<i<<" "<<photo<<endl;
		}*/
	}
	for(int i=0;i<=k;i++)ans=min(ans,DP[p][i]);
	
	return ans;
}

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