| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1339692 | orgiloogii | Roller Coaster Railroad (IOI16_railroad) | C++20 | 0 ms | 0 KiB |
#include "railroad.h"
#include <bits/stdc++.h>
using namespace std;
long long plan_roller_coaster(vector<int> s, vector<int> t) {
int n = (int) s.size();
int m = (1 << n);
vector <vector <long long>> dp(m, vector <long long>(n, LLONG_MAX));
for (int i = 0;i < n;i++) {
dp[(1 << i)][i] = 0;
}
for (int mask = 1; mask < m; mask++) {
for (int i = 0;i < n;i++) {
if ((mask & (1 << i)) != 0) continue;
for (int j = 0;j < n;j++) {
if ((mask & (1 << j)) == 0) continue;
if (t[j] <= s[i]) {
dp[mask + (1 << i)][i] = min(dp[mask + (1 << i)][i], dp[mask][j]);
}
else {
dp[mask + (1 << i)][i] = min(dp[mask + (1 << i)][i], dp[mask][j] + (t[j] - s[i]));
}
}
}
}
long long ans = LLONG_MAX
for (int i = 0;i < n;i++) {
ans = min(ans, dp[(1 << n) - 1][i]);
}
return 0;
}
