/** * author: milos * created: 08.04.2021 21:49:49 **/ #include <bits/stdc++.h> using namespace std; long long plan_roller_coaster(vector<int> s, vector<int> t) { int n = (int) s.size(); const long long inf = 1e18; vector<vector<long long>> dp(1 << n, vector<long long>(n, inf)); for (int i = 0; i < n; i++) { dp[0][i] = 0; dp[(1 << i)][i] = 0; } for (int i = 1; i < (1 << n); i++) { for (int j = 0; j < n; j++) { if (dp[i][j] != inf) { continue; } if (i & (1 << j)) { for (int k = 0; k < n; k++) { if (j != k && i & (1 << k)) { dp[i][j] = min(dp[i][j], dp[i - (1 << j)][k] + max(0, t[k] - s[j])); } } } } } long long ans = inf; for (int i = 0; i < n; i++) { ans = min(ans, dp[(1 << n) - 1][i]); } return ans; }