Submission #468032

#	Time	Username	Problem	Language	Result	Execution time	Memory
468032		Pietra	Roller Coaster Railroad (IOI16_railroad)	C++14	34 / 100	126 ms	88352 KiB

railroad

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

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

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

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) ; 
	S.push_back(1), T.push_back(0) ;
	for(int i = 0 ; i < n ; i++) S.push_back(s[i]), T.push_back(t[i]) ; 
	S.push_back(1), T.push_back(0) ;  
	return solve(1, 0) ;  
} 

/*
int main(){

	cin >> n ; 

	memset(dp, -1, sizeof dp) ; 
	S.push_back(1), T.push_back(0) ; 
	for(int i = 0 ; i < n ; i++){
		int a, b ; 
		cin >> a >> b ;
		S.push_back(a), T.push_back(b) ;  
	} 
	S.push_back(1), T.push_back(0) ; 
	cout << solve(1, 0) << "\n" ; 

}*/

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