# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1265571 | gustavo_d | Roller Coaster Railroad (IOI16_railroad) | C++20 | 25 ms | 8620 KiB |
#include "railroad.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 16;
ll dp[MAXN][1 << MAXN];
ll plan_roller_coaster(vector<int> s, vector<int> t) {
int n = (int) s.size();
for (int i=0; i<n; i++) {
for (int m=0; m<(1 << n); m++) dp[i][m] = 1e18;
}
for (int m=1; m<(1 << n); m++) {
vector<int> v;
for (int i=0; i<n; i++) {
if (((1 << i) & m) != 0) v.push_back(i);
}
// for (int i : v) cout << i << ' ';
// cout << ':';
if (v.size() == 1) {
dp[v[0]][m] = 0;
}
for (int i : v) {
for (int j : v) {
if (i == j) continue;
assert ((m-(1<<i)) == (m^(1<<i)));
// cout << j << "->" << i << '=' << t[j] << ' ' << s[i] << ' ' << t[j]-s[i] << endl;
dp[i][m] = min(
dp[i][m],
dp[j][m ^ (1 << i)] + max(0, t[j]-s[i])
);
}
// cout << dp[i][m] << ' ';
}
// cout << endl;
}
ll ans = 1e18;
for (int i=0; i<n; i++) ans = min(ans, dp[i][(1 << n)-1]);
return ans;
}
Compilation message (stderr)
# | 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... |