| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 558750 | elazarkoren | Shortcut (IOI16_shortcut) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "railroad.h"
#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define chkmin(a, b) a = min(a, b)
#define chkmax(a, b) a = max(a, b)
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef vector<pii> vii;
const ll infinity = 1e18;
const int MAX_N = 16;
ll dp[1 << MAX_N][MAX_N];
ll plan_roller_coaster(vi s, vi t) {
int n = s.size();
vi ind(n);
iota(all(ind), 0);
sort(all(ind), [&] (int i, int j) {
return t[i] < t[j];
});
ll ans = 0;
for (int i = 0; i < n - 1; i++) {
ans += max(0, t[i] - s[i + 1]);
}
return ans;
// for (int i = 1; i < (1 << n); i++) {
// for (int j = 0; j < n; j++) dp[i][j] = infinity;
// if (__builtin_popcount(i) == 1) {
// dp[i][__builtin_ctz(i)] = 0;
// continue;
// }
// for (int j = 0; j < n; j++) {
// if (!((i >> j) & 1)) continue;
// int mask = i ^ (1 << j);
// for (int k = 0; k < n; k++) {
// chkmin(dp[i][j], dp[mask][k] + max(0, t[k] - s[j]));
// }
// }
// }
// ll ans = infinity;
// for (int i = 0; i < n; i++) chkmin(ans, dp[(1 << n) - 1][i]);
// return ans;
}