This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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(mask == (1<<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:30:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
30 | for(int i = 0 ; i < s.size() ; i++) S[i] = s[i], T[i] = t[i] ;
| ~~^~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |