| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 106651 | popovicirobert | Palembang Bridges (APIO15_bridge) | 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 <bits/stdc++.h>
#define lsb(x) (x & (-x))
#define ll long long
#define ull unsigned long long
// 217
// 44
using namespace std;
const ll INF = 1e18;
inline void solve(vector < pair <int, int> > &arr, vector <ll> &sol) {
int sz = arr.size();
sol.resize(sz);
multiset <int> mst1, mst2;
ll sum1 = 0, sum2 = 0;
for(int i = 0; i < sz; i++) {
mst2.insert(arr[i].first);
sum2 += arr[i].first;
mst2.insert(arr[i].second);
sum2 += arr[i].second;
while(mst1.size() < i + 1) {
mst1.insert(*mst2.begin());
sum1 += *mst2.begin();
sum2 -= *mst2.begin();
mst2.erase(mst2.begin());
}
int cur = *prev(mst1.end());
sol[i] = 1LL * mst1.size() * cur - sum1 + sum2 - 1LL * mst2.size() * cur;
}
}
int main() {
//ifstream cin("A.in");
//ofstream cout("A.out");
int i, n, k;
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin >> k >> n;
vector < pair <int, int> > arr;
ll ans = 0;
for(i = 1; i <= n; i++) {
char a, b;
int x, y;
cin >> a >> x >> b >> y;
if(x > y) {
swap(x, y);
}
if(a != b) {
arr.push_back({x, y});
}
else {
ans += y - x;
}
}
sort(arr.begin(), arr.end(), [&](const pair <int, int> &a, const pair <int, int> &b) {
return a.first + a.second < b.first + b.second;
});
if(k == 1) {
vector <int> vals;
ll tot = 0;
for(auto it : arr) {
vals.push_back(it.first);
vals.push_back(it.second);
tot += it.first + it.second;
}
sort(vals.begin(), vals.end());
ll mn = INF, sum = 0;
for(i = 0; i < vals.size(); i++) {
sum += vals[i];
mn = min(mn, 1LL * vals[i] * (i + 1) - sum + (tot - sum) - 1LL * vals[i] * (vals.size() - i - 1));
}
cout << ans + mn + arr.size();
return 0;
}
vector <ll> sol_l, sol_r;
solve(arr, sol_l);
reverse(arr.begin(), arr.end());
solve(arr, sol_r);
int sz = arr.size();
ll mn = min(sol_l[sz - 1], sol_r[sz - 1]);
for(int i = 0; i < sz - 1; i++) {
mn = min(mn, sol_l[i] + sol_r[sz - i - 2]);
}
cout << ans + mn + arr.size();
//cin.close();
//cout.close();
return 0;
}