이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
/*
1 5
B 0 A 4
B 1 B 3
A 5 B 7
B 2 A 6
B 1 A 7
*/
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll lsum;
ll rsum;
multiset<int> lval;
multiset<int> rval;
void add(int u, int v) {
rsum += u;
rval.insert(u);
rsum += v;
rval.insert(v);
while (rval.size() > lval.size()) {
int x = *rval.begin();
rsum -= x;
rval.erase(rval.find(x));
lsum += x;
lval.insert(x);
}
while (*--lval.end() > *rval.begin()) {
int x = *--lval.end();
int y = *rval.begin();
lsum -= x;
lval.erase(lval.find(x));
lsum += y;
lval.insert(y);
rsum -= y;
rval.erase(rval.find(y));
rsum += x;
rval.insert(x);
}
}
vector<ll> eval(vector<pair<int, int>> vals) {
lsum = 0;
lval.clear();
rsum = 0;
rval.clear();
int n = vals.size();
vector<ll> f(1, 0);
for (int i = 0; i < n; ++i) {
add(vals[i].first, vals[i].second);
f.push_back(rsum - lsum);
}
return f;
}
int main() {
ios_base::sync_with_stdio(false);
int k, n;
cin >> k >> n;
ll ans = 0;
vector<pair<int, int>> vals;
for (int i = 0; i < n; ++i) {
string p, q;
int s, t;
cin >> p >> s >> q >> t;
if (p == q) {
ans += abs(s - t);
} else {
++ans;
vals.emplace_back(s, t);
}
}
sort(vals.begin(), vals.end(), [&](pair<int, int> u, pair<int, int> v) {
return u.first + u.second < v.first + v.second;
});
auto f = eval(vals);
reverse(vals.begin(), vals.end());
auto g = eval(vals);
int m = vals.size();
ll mn = 1e18;
for (int i = 0; i < (k == 1 ? 1 : m); ++i) {
mn = min(mn, f[i] + g[m - i]);
}
cout << ans + mn << "\n";
}
# | 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... |