# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
789799 | 2023-07-22T04:38:59 Z | mindiyak | Roller Coaster Railroad (IOI16_railroad) | C++14 | 0 ms | 0 KB |
#include "railroad.h" #include <vector> #include <algorithm> #include <iostream> #include <unordered_map> #include <bitset> #define pb push_back using namespace std; #define ll long long vector<int>S; vector<int>T; vector<vector<ll>> dp((1<<18),vector<ll>(18,1e16)); int calc_cost(int i,int j){ return max(T[i]-S[j],0); } long long plan_roller_coaster(std::vector<int> s, std::vector<int> t) { int n = (int) s.size(); S = s;T = t; dp[1][0] = 0; for(int i=0;i<(1<<n);i++){ for(int j=0;j<n;j++){ if((i&(1<<j)) == 0){ for(int k=0;k<n;k++){ if((i&(1<<k)) != 0){ // bitset<8> x(i); // cout << x << " add " << j << " through k " << k << endl; dp[i|(1<<j)][j] = min(dp[i|(1<<j)][j],dp[i][k]+calc_cost(k,j)); } } } } } ll ans = LLONG_MAX; for(int i=0;i<n;i++){ ans = min(ans,dp[(1<<n)-1][i]); } return ans; }