이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define int long long
/*
K = 1:
For the bridge at i, each (x, y) incurs a cost |x-i| + |y-i|,
which can be minimized by choosing the median of these points.
K = 2:
When sorted by (x + y), it can be proved that the first bridge
is better for some prefix of pairs (x, y). Also, the median
is monotonic for increasing prefixes, so calculate for each.
*/
int K, N, ext, ans, curCost, suf[1<<17];
vector<array<int, 2>> a;
priority_queue<int> L, R; // for R: value *= -1
int l, r;
void put(int v) {
if(empty(L) || v <= L.top())
L.push(+v), l += v;
else
R.push(-v), r += v;
if(size(L) < size(R)) {
L.push(v = -R.top()), R.pop();
r -= v;
l += v;
}
if(size(L) > size(R) + 1) {
R.push(v = -L.top()), L.pop();
r -= v;
l += v;
}
}
int32_t main() {
ios::sync_with_stdio(0), cin.tie(0);
cin >> K >> N;
for(int i = 0, s, t; i < N; ++i) {
char p, q;
cin >> p >> s >> q >> t;
if(p == q) ext += t - s;
else {
++ext;
a.push_back({s, t});
}
}
N = size(a);
sort(begin(a), end(a) , [&](const auto &i, const auto &j) {
return i[0] + i[1] < j[0] + j[1];
});
for(int i = N; i--; ) {
put(a[i][0]), put(a[i][1]);
suf[i] = r - l;
}
ans = suf[0];
if(K > 1) {
L = R = priority_queue<int> ();
l = r = 0;
for(int i = 0; i < N; ++i) {
put(a[i][0]), put(a[i][1]);
ans = min(ans, r - l + suf[i+1]);
}
}
cout << ans + ext;
}
# | 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... |