# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
778295 | 2023-07-10T08:17:28 Z | vjudge1 | Roller Coaster Railroad (IOI16_railroad) | C++17 | 0 ms | 0 KB |
#include "railroad.h" #include <bits/stdc++.h> using namespace std; #include "mol.h" #define sp " " #define endl "\n" #define pb push_back #define pii pair<int, int> #define st first #define nd second #define N 17 #define ll long long ll dp[N][(1<<N)]; const ll INF = 2e18 + 7; long long plan_roller_coaster(vector<int> s, vector<int> t) { int n = (int) s.size(); for (int i = 0; i < n; i++) dp[(1<<n) - 1][i] = 0; for (int i = (1<<n) - 2; i > 0; i--){ for (int j = 0; j < n; j++){ if (i & (1<<j)){ dp[i][j] = INF; for (int k = 0; k < n; k++){ if (i & (1<<k)) continue; dp[i][j] = min(dp[i][j], dp[i | (1<<k)][k] + max((int)0, t[j] - s[k])); } } } } ll ans = INF; for (int i = 0; i < n; i++) ans = min(ans, dp[(1<<i)][i]); return ans; }