| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 296127 | RealSuperman1 | 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 <bits/stdc++.h>
#define ll long long
#define int long long
#define pb push_back
#define fi first
#define se second
#define pll pair<long long, long long>
#define pii pair<int, int>
using namespace std;
const ll INF = 1e18;
int n;
bool cmp(pii x, pii y) {
return x.fi > y.fi;
}
ll case3(vector <int> s, vector <int> t) {
vector <pii> t1(n);
for (int i = 0; i < n; i++)
t1[i] = {t[i], i};
sort(t1.begin(), t1.end(), cmp);
// for (auto to : s1)
// cout << to.fi << " " << to.se << endl;
// cout << endl;
// return 0;
vector <int> nx(n, -1);
set <pii> sn = {};
for (int i = 0; i < n; i++)
sn.insert({s[i], i});
set <pii>::iterator it;
for (int i = 0; i < n; i++) {
it = sn.lower_bound({t1[i].fi, 0});
if (it == sn.end())
continue;
pii val = *it;
if (val.se == t1[i].se)
it = sn.upper_bound(val);
if (it == sn.end())
continue;
val = *it;
nx[t1[i].se] = val.se;
// cout << t1[i].se << "->" << val.se << endl;
sn.erase(it);
if (sn.size() == 1)
break;
}
if (sn.size() == 1)
return 0ll;
vector <int> s_new, t_new;
for (set<pii>::iterator it = sn.begin(); it != sn.end(); it++) {
int curt, curs;
pii val = *it;
int u = val.se;
curs = s[u];
while (nx[u] != -1)
u = nx[u];
curt = t[u];
s_new.pb(curs);
t_new.pb(curt);
}
ll ans = 0, sumt = 0, sums = 0;
for (int i = 0; i < s_new.size(); i++) {
// cout << s_new[i] << " ";
sums += s_new[i] * 1ll;
}
// cout << endl;
pii mx1 = {-1, -1}, mx2 = {-1, -1};
for (int i = 0; i < t_new.size(); i++) {
// cout << t_new[i] << " ";
sumt += t_new[i] * 1ll;
if (t_new[i] >= mx1.fi) {
mx2 = mx1;
mx1 = {t_new[i], i};
} else if (t_new[i] >= mx2.fi)
mx2 = {t_new[i], i};
}
// cout << endl;
ll mn = INF;
for (int i = 0; i < s_new.size(); i++) {
if (mx1.se != i)
mn = min(mn, s_new[i] * 1ll - mx1.fi * 1ll);
else
mn = min(mn, s_new[i] * 1ll - mx2.fi * 1ll);
}
// cout << mx1.fi << " " << mx1.se << endl;
// cout << mx2.fi << " " << mx2.se << endl;
return sumt - sums + mn;
}
ll plan_roller_coaster(vector <int> s, vector <int> t) {
n = s.size();
if (n > 16 || true) {
return case3(s, t);
}
vector < vector <ll> > w;
vector < vector <ll> > dp;
w.resize(n);
for (int i = 0; i < n; i++) {
w[i].resize(n);
for (int j = 0; j < n; j++) {
if (i == j)
continue;
w[i][j] = max(0, t[i] - s[j]);
}
}
dp.resize((1 << n));
for (int mask = 0; mask < (1 << n); mask++) {
dp[mask].resize(n);
for (int i = 0; i < n; i++)
dp[mask][i] = INF;
}
for (int i = 0; i < n; i++)
dp[0][i] = 0;
vector <int> b;
for (int mask = 1; mask < (1 << n); mask++) {
b.clear();
for (int i = 0; i < n; i++)
if (1 & (mask >> i))
b.pb(i);
if (b.size() == 1) {
dp[mask][b[0]] = 0;
continue;
}
for (int i = 0; i < b.size(); i++)
for (int j = 0; j < b.size(); j++) {
if (i == j)
continue;
int mask1 = (mask ^ (1 << b[i]));
dp[mask][b[i]] = min(dp[mask][b[i]], dp[mask1][b[j]] + w[b[j]][b[i]]);
}
}
ll ans = INF;
for (int i = 0; i < n; i++)
ans = min(ans, dp[(1 << n) - 1][i]);
return ans;
}