| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 241683 | godwind | Roller Coaster Railroad (IOI16_railroad) | C++14 | 0 ms | 0 KiB |
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 "railroad.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <random>
#include <set>
#include <map>
#include <queue>
#include <cstring>
#include <cmath>
#include <bitset>
#include <iomanip>
#include <functional>
using namespace std;
template<typename T> void uin(T &a, T b) {
if (b < a) a = b;
}
const long long INF = 1e18 + 228;
long long dp[(1 << 17) + 17][16];
long long plan_roller_coaster(vector<int> s, vector<int> t) {
int n = (int)s.size();
if (n <= 16) {
for (int i = 0; i < (1 << n); ++i) {
for (int j = 0; j < n; ++j) {
dp[i][j] = INF;
}
}
for (int fir = 0; fir < n; ++fir) {
dp[1 << fir][fir] = 0;
}
for (int mask = 0; mask < (1 << n); ++mask) {
for (int last = 0; last < n; ++last) {
if (dp[mask][last] != INF) {
for (int new_last = 0; new_last < n; ++new_last) {
if ((mask >> new_last) & 1) continue;
long long cur = dp[mask][last] + max(0LL, t[last] - s[new_last]);
uin(dp[mask | new_last][new_last], cur);
}
}
}
}
long long answer = INF;
for (int last = 0; last < n; ++last) {
uin(answer, dp[(1 << n) - 1][last]);
}
return answer;
}
return 0;
}