Submission #468030

#	Time	Username	Problem	Language	Result	Execution time	Memory
468030		Pietra	Roller Coaster Railroad (IOI16_railroad)	C++14	0 / 100	121 ms	167504 KiB

railroad

#include<bits/stdc++.h>
#include "railroad.h"
using namespace std ; 

const long long inf = 1e18 ; 
const int maxn = 20 ; 

long long dp[(1<<maxn)][maxn], n, S[maxn], T[maxn] ; 

long long solve(int mask, int i){
	
	if(__builtin_popcount(mask) == n+1) return 0 ; 
	long long &mp = dp[mask][i] ;
	
	if(mp != -1) return mp ;   
	mp = inf ; 
	for(int j = 0 ; j <= n ; j++){
		if(mask&(1<<j)) continue ; 
		mp = min(mp, max(0LL, T[i] - S[j]) + solve(mask|(1<<j), j)) ; 
	}

	return mp ; 

}

long long plan_roller_coaster(vector<int> s, vector<int> t){
	n = (int) s.size() ; 
	memset(dp, -1, sizeof dp) ; 
	for(int i = 0 ; i < s.size() ; i++) S[i] = s[i], T[i] = t[i] ; 
	return solve(1, 0) ;  
} 
/*
int main(){

	cin >> n ; 

	memset(dp, -1, sizeof dp) ; 

	for(int i = 0 ; i < n ; i++) cin >> S[i] >> T[i] ; 

	cout << solve(1, 0) << "\n" ; 

}*/

Compilation message (stderr)

railroad.cpp: In function 'long long int plan_roller_coaster(std::vector<int>, std::vector<int>)':
railroad.cpp:29:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |  for(int i = 0 ; i < s.size() ; i++) S[i] = s[i], T[i] = t[i] ;
      |                  ~~^~~~~~~~~~

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