Submission #73016

#	Time	Username	Problem	Language	Result	Execution time	Memory
73016		KLPP	Roller Coaster Railroad (IOI16_railroad)	C++14	0 / 100	147 ms	7112 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];
	for(int i=0;i<n;i++){
		arr[i].first=s[i];
		arr[i].second=t[i];
	}
	sort(arr,arr+n);
	int maximo[n];
	for(int i=0;i<n;i++){
		int hi,lo;
		lo=-1;
		hi=n;
		while(hi-lo>1){
			int mid=(hi+lo)/2;
			if(arr[i].second<=arr[mid].first)hi=mid;
			else lo=mid;
		}
		maximo[i]=hi;
		//cout<<hi<<endl;
	}
	int sum[n];
	for(int i=0;i<n;i++){
		sum[i]=0;
	}
	for(int i=0;i<n;i++){
		if(maximo[i]<n)sum[maximo[i]]++;
	}
	for(int i=1;i<n;i++){
		sum[i]+=sum[i-1];
	}
	//for(int i=0;i<n;i++)cout<<sum[i]<<endl;
	bool b[n];
	for(int i=0;i<n;i++){
		b[i]=true;
	}
	int next[n];
	for(int i=0;i<n;i++){
		int minimo=0;
		for(int j=0;j<n;j++){
			if(b[j] && sum[minimo]-minimo>sum[j]-j)minimo=j;
		}
		if(i>0 && minimo<maximo[next[i-1]])return 0;
		if(sum[minimo]<minimo)return 1;
		if(sum[minimo]>minimo)return 0;
		b[minimo]=false;
		for(int j=maximo[minimo];j<n;j++){
			sum[j]--;
		}
		next[i]=minimo;
	}
	return 0;
}

Compilation message (stderr)

railroad.cpp: In function 'long long int trabalha(int, int)':
railroad.cpp:25:21: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
   if(BIT(mask,i) & i!=start){
                    ~^~~~~~~

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