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 ll long long
using namespace std;
int n, k, in1, in2, mxl, mnr;
char c1, c2;
vector<pair<int, int>> v;
multiset<int> s1, s2;
ll pref[100010], suff[100010], su1, su2, res, ans;
bool cmp(const pair<int, int> &a, const pair<int, int> &b) {
return a.first+a.second < b.first+b.second;
}
void insertVal(int in) {
if(s1.size() <= s2.size()) {
s1.insert(in);
su1 += in;
} else {
s2.insert(in);
su2 += in;
}
if(s1.size() && s2.size() && *s1.rbegin() > *s2.begin()) {
mxl = *s1.rbegin();
mnr = *s2.begin();
su1 += mnr - mxl;
su2 += mxl - mnr;
s1.insert(mnr);
s1.erase(s1.find(mxl));
s2.insert(mxl);
s2.erase(s2.find(mnr));
}
}
int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> k >> n;
for(int i=0; i<n; i++) {
cin >> c1 >> in1 >> c2 >> in2;
if(c1 == c2) {
res += abs(in1 - in2);
continue;
}
v.push_back({in1, in2});
}
sort(v.begin(), v.end(), cmp);
res += v.size();
for(int i=0; i<v.size(); i++) {
insertVal(v[i].first);
insertVal(v[i].second);
pref[i] = (s1.size()-s2.size())*(*s1.rbegin()) - su1 + su2;
}
ans = pref[v.size()-1];
if(k == 1) {
cout << ans+res;
return 0;
}
s1.clear();
s2.clear();
su1 = 0;
su2 = 0;
for(int i=v.size()-1; i>0; i--) {
insertVal(v[i].first);
insertVal(v[i].second);
suff[i] = (s1.size()-s2.size())*(*s1.rbegin()) - su1 + su2;
}
for(int i=0; i<v.size()-2; i++) {
ans = min(ans, pref[i]+suff[i+1]);
}
cout << ans+res;
return 0;
}
Compilation message (stderr)
bridge.cpp: In function 'int main()':
bridge.cpp:48:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
48 | for(int i=0; i<v.size(); i++) {
| ~^~~~~~~~~
bridge.cpp:67:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
67 | for(int i=0; i<v.size()-2; 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... |