Submission #57833

#	Time	Username	Problem	Language	Result	Execution time	Memory
57833		robert	Roller Coaster Railroad (IOI16_railroad)	C++14	34 / 100	163 ms	25172 KiB

railroad

#include <iostream>
#include <vector>
#include <cstring>

using namespace std;

vector<int> s, t;

long long m[20][100100];

long long solve(long long p, long long sel){
	if(sel==((1<<(s.size()-1))-1))
		return 0;
	if(m[p][sel]!=-1)
		return m[p][sel];
	long long ret = 1e15;
	for(long long x=0ll; x<s.size()-1; x++){
		if(((1ll<<x)&sel)==0ll){
			//not selected
			ret = min(ret, solve(x, sel|(1<<x))+((s[x]<t[p])?(t[p]-s[x]):0ll));
		}
	}
	return m[p][sel] = ret;
}

long long plan_roller_coaster(vector<int> s_c, vector<int> t_c){
	s = s_c;
	t = t_c;
	s.push_back(1);
	t.push_back(1);
	memset(m, -1, sizeof(m));
	if(s_c.size()>100)
		return 0;
	return solve(t.size()-1, 0);
}
/*
int main(){
	vector<int> s_c = {1, 4, 5, 6}, t_c = {7, 3, 8, 6};
	cout << plan_roller_coaster(s_c, t_c) << endl;
}*/

Compilation message (stderr)

railroad.cpp: In function 'long long int solve(long long int, long long int)':
railroad.cpp:17:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(long long x=0ll; x<s.size()-1; x++){
                       ~^~~~~~~~~~~

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