Submission #59584

#	Time	Username	Problem	Language	Result	Execution time	Memory
59584		KLPP	Roller Coaster Railroad (IOI16_railroad)	C++14	34 / 100	2037 ms	9712 KiB

railroad

#include "railroad.h"
#include<iostream>

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();
	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));
	}
	/*for(int i=0;i<n;i++){
		for(int j=0;j<(1<<n);j++)cout<<DP[i][j]<<" ";
		cout<<endl;
	}*/
	return ans;
}

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: 11 / 11
• Subtask 2: 23 / 23
• Subtask 3: 0 / 30
• Subtask 4: 0 / 36