제출 #89437

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
89437		KLPP	Aliens (IOI16_aliens)	C++14	25 / 100	2031 ms	8424 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 Cost[1000000];
lld sq(lld x){
	return x*x;
}
lld sq2(lld x){
	if(x>0)return x*x;
	return 0;
}
void print(pair<lld,lld> a){
	cout<<a.first<<" "<<a.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);
	}
	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++){
		for(int i=0;i<=p;i++){
			DP[i][photo]=min(DP[i][photo],DP[i][photo-1]);
			for(int j=0;j<i;j++){
				DP[i][photo]=min(DP[i][photo],DP[j][photo-1]-Cost[j]+sq(arr[i-1].second-arr[j].first+1));
			}
		}
	}
	/*for(int photo=0;photo<=k;photo++){
		for(int i=0;i<=p;i++){
			cout<<DP[i][photo]<<" ";
		}cout<<endl;
	}*/
	
	return DP[p][k];
}

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