Submission #67218

#	Time	Username	Problem	Language	Result	Execution time	Memory
67218		KLPP	Aliens (IOI16_aliens)	C++14	12 / 100	22 ms	4636 KiB

aliens

#include "aliens.h"
#include<algorithm>
#include<iostream>
#include<vector>
#include<stdio.h>
using namespace std;
#define INF 1000000000000000000
typedef pair<long long int,long long int> pii;
vector<pair<long long int,long long int> >arr;
long long int DP[50000][4001];
int p;
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;
}
long long int computecost(int i, int j){
	if(j<i)return INF;
	long long int R=arr[j].second-arr[i].first+1;
	R*=R;
	if(i>0){
		R-=sq2(arr[i-1].second-arr[i].first+1);
	}
	return R;
}
void compute(int x, int y, int photos, int a, int b){
	if(x>y)return;
	int mid=(x+y)/2;
	int best=-1;
	for(int i=a;i<=b;i++){
		if(DP[mid][photos]>DP[i][photos-1]+computecost(i,mid-1)){
			best=i;
			DP[mid][photos]=DP[i][photos-1]+computecost(i,mid-1);
		}
	}
	compute(x,mid-1,photos,a,best);
	compute(mid+1,y,photos,best,b);
}
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]);
			//printf("%lld %lld \n",points[i].first,points[i].second);
		}
	}
	p=arr.size();
	//cout<<p<<endl;
	/*for(int i=0;i<p;i++){
		for(int j=i;j<p;j++){
			cout<<computecost(i,j)<<" ";
		}cout<<endl;
	}*/
	for(int i=0;i<=k;i++){
		for(int j=0;j<=p;j++){
			DP[j][i]=INF;
		}
	}
	DP[0][0]=0;
	for(int photo=1;photo<=k && photo<=p;photo++){
		compute(0,p,photo,0,p);
		//for(int j=0;j<=p;j++)cout<<DP[j][photo]<<" ";
		//cout<<endl;
	}
	long long int ans=INF;
	for(int i=0;i<=k;i++)ans=min(ans,DP[p][i]);
	
	return ans;
}

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