이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "railroad.h"
#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
#define pb push_back
typedef long long ll;
typedef pair<ll, ll> ii;
#define MAXN 18
#define LOG 20
#define INF 1001001001001001001LL
ll dp[1 << MAXN][LOG], reza = INF;
//set<ii> v;
long long plan_roller_coaster(std::vector<int> s, std::vector<int> t) {
int n = (int) s.size();
for (int i = 0; i < (1 << n); i++)
for (int j = 0; j < n; j++)
dp[i][j] = INF;
for (int i = 0; i < n; i++)
dp[1 << i][i] = 0;
for (int i = 1; i < (1 << n); i++) {
if (__builtin_popcount(i) == 1) continue;
for (int j = 0; j < n; j++) {
if (i & (1 << j)) {
for (int k = 0; k < n; k++) {
if (!(i & (1 << k)) || j == k) continue;
dp[i][j] = min(dp[i][j], dp[i ^ (1 << j)][k] + (ll)max(0, t[k] - s[j]));
}
if (i == (1 << n) - 1) {
reza = min(reza, dp[i][j]);
}
}
}
}
return reza;
/*for (int i = 0; i < n; i++) {
v.insert({s[i], t[i]});
//cout << t[i]<<' '<<s[i]<<endl;
}
ll ri = 1;
while (!v.empty()) {
auto cu = v.lower_bound({ri, 0});
if (cu == v.end()) return 1;
ri = cu -> Y;
v.erase(cu);
cout << cu -> X <<' '<<cu -> Y<<endl;
}
return 0;*/
}
# | 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... |