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 all(c) c.begin(), c.end()
#define pb push_back
#define ll long long
#define x first
#define y second
using namespace std;
long long min_total_length(std::vector<int> r, std::vector<int> b) {
int n = r.size();
int m = b.size();
bool taken[200005] = {};
vector<pair<ll,pair<int,int>>> ve;
for (int i = 0; i < n; i++) {
int it = lower_bound(all(b),r[i])-b.begin();
if (it == m) {
it--;
ve.pb({r[i]-b[it],{i,it+n}});
} else {
ll dist = b[it]-r[i];
int id = it;
it--;
if (it >= 0 && r[i]-b[it] < dist) {
dist = r[i]-b[it];
id--;
}
ve.pb({dist,{i,it+n}});
}
}
for (int i = 0; i < m; i++) {
int it = lower_bound(all(r),b[i])-r.begin();
if (it == n) {
it--;
ve.pb({b[i]-r[it],{i+n,it}});
} else {
int dist = r[it]-b[i];
int id = it;
it--;
if (it >= 0 && b[i]-r[it] < dist) {
dist = b[i]-r[it];
id--;
}
ve.pb({dist,{i+n,it}});
}
}
sort(all(ve));
reverse(all(ve));
ll ans = 0;
for (auto k : ve) {
if (taken[k.y.x]) continue;
taken[k.y.x] = 1;
taken[k.y.y] = 1;
ans += k.x;
}
return ans;
}
# | 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... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |