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 <iostream>
#include <set>
#include <vector>
#include <algorithm>
using namespace std;
multiset<int> st, dr;
long long ssum = 0, dsum = 0;
bool cmp(pair<int, int> a, pair<int, int> b) {
return a.first + a.second < b.first + b.second;
}
void adauga(int nr) {
int mid = st.empty() ? 10000001 : *st.rbegin();
if (nr <= mid) {
st.insert(nr);
ssum += nr;
} else {
dr.insert(nr);
dsum += nr;
}
if (dr.size() + 1 < st.size()) {
int auxs = *st.rbegin();
st.erase(st.find(auxs));
dr.insert(auxs);
ssum -= auxs;
dsum += auxs;
} else if (st.size() < dr.size()) {
int auxs = *dr.begin();
dr.erase(dr.find(auxs));
st.insert(auxs);
dsum -= auxs;
ssum += auxs;
}
}
int main() {
int n, k;
cin >> k >> n;
vector<pair<int, int>> poz;
long long ans = 0, fel = 0;
for (int i = 1; i <= n; i++) {
int a, b;
char c, cc;
cin >> c >> a >> cc >> b;
if (c == cc)
fel += abs(a - b);
else
poz.push_back({a, b});
}
sort(poz.begin(), poz.end(), cmp);
fel += poz.size();
vector<long long> api(poz.size());
for (int i = 0; i < poz.size(); i++) {
adauga(poz[i].first);
adauga(poz[i].second);
api[i] = dsum - ssum;
}
ans = api[poz.size() - 1];
if (k == 2) {
st.clear();
dr.clear();
ssum = dsum = 0;
for (int i = poz.size() - 1; i >= 0; i--) {
adauga(poz[i].first);
adauga(poz[i].second);
if (i > 0) {
ans = min(ans, dsum - ssum + api[i - 1]);
}
}
}
cout << ans + fel;
return 0;
}
Compilation message (stderr)
bridge.cpp: In function 'int main()':
bridge.cpp:64:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
64 | for (int i = 0; i < poz.size(); i++) {
| ~~^~~~~~~~~~~~
# | 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... |