| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 958829 | MinaRagy06 | Shortcut (IOI16_shortcut) | C++17 | 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 <bits/stdc++.h>
#include "railroad.h"
#ifdef MINA
#include "grader.cpp"
#endif
using namespace std;
#define ll long long
ll plan_roller_coaster(vector<int> in, vector<int> out) {
int n = in.size();
set<array<int, 2>> s;
for (int i = 0; i < n; i++) {
s.insert({in[i], out[i]});
}
vector<array<int, 2>> a;
while (s.size()) {
array<int, 2> val = *s.begin();
s.erase(s.begin());
int st = val[0];
while (1) {
auto it = s.lower_bound({val[1], 0});
if (it == s.end()) {
break;
}
val = *it;
s.erase(it);
}
int en = val[1];
a.push_back({st, en});
}
n = a.size();
ll sum = 0;
for (int i = 0; i < n; i++) {
sum += a[i][1] - a[i][0];
}
ll ans = 1e18;
for (int x = 0; x < n; x++) {
for (int y = 0; y < n; y++) {
if (x == y) continue;
ans = min(ans, sum + a[x][0] - a[y][1]);
}
}
return ans;
}