제출 #92582

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
92582		KLPP	Roller Coaster Railroad (IOI16_railroad)	C++14	0 / 100	126 ms	9872 KiB

railroad

#include "railroad.h"
#include<iostream>
#include<algorithm>
using namespace std;
//long long DP[20][100000];
int n;
/*long long graph[20][20];
long long f(int x){
	if(x>0)return x;
	return 0;
}
long long min(int x, int y){
	if(x<y)return x;
	return y;
}
bool BIT(int n, int k){
	if((n >> (k )) & 1)return true;
	return false;
}
long long trabalha(int start, int mask){
	if(DP[start][mask]!=-1)return DP[start][mask];
	//cout<<start<<" "<<mask<<endl;
	DP[start][mask]=200000000000;
	for(int i=0;i<n;i++){
		if(BIT(mask,i) & i!=start){
			DP[start][mask]=min(DP[start][mask],trabalha(i,mask^(1<<(start)))+graph[i][start]);
		}
	}
	if(DP[start][mask]==200000000000)DP[start][mask]=0;
	return DP[start][mask];
}*/

long long plan_roller_coaster(std::vector<int> s, std::vector<int> t) {
	n=s.size();
	/*if(n<=16){
	for(int i=0;i<n;i++){//cout<<t[i]<<" "<<s[i]<<endl;
		for(int j=0;j<n;j++){
			graph[i][j]=f(t[i]-s[j]);//ir de i para j
			//cout<<graph[i][j]<<" ";
		}//cout<<endl;
	}
	long long ans=200000000000;
	for(int i=0;i<n;i++){
		for(int j=0;j<(1<<n);j++)DP[i][j]=-1;
	}
	for(int i=0;i<n;i++){
		ans=min(ans,trabalha(i,(1<<n)-1));
	}
	
	return ans;
	}*/
	pair<int,int> arr[n+1];
	for(int i=0;i<n;i++)arr[i]=pair<int,int>(s[i],t[i]);
	arr[n]=pair<int,int>(1000000000,0);
	n++;
	sort(arr,arr+n);
	int allow[n];
	for(int i=0;i<n;i++){
		int hi,lo;
		hi=n;
		lo=-1;
		while(hi-lo>1){
			int mid=(hi+lo)/2;
			if(arr[mid].first<arr[i].second){
				lo=mid;
			}else hi=mid;
		}
		allow[i]=hi;
		//cout<<i<<" "<<hi<<" "<<arr[i].first<<" "<<arr[i].second<<endl;
	}
	sort(allow,allow+n);
	int m=n+1;
	for(int i=n-1;i>-1;i--){
		m=min(m,allow[i]);
		//cout<<m<<" "<<i<<endl;
		if(m>i)return 1;
	}
	return 0;
}

• Subtask 1: 0 / 11
• Subtask 2: 0 / 23
• Subtask 3: 0 / 30
• Subtask 4: 0 / 36