제출 #981903

#제출 시각아이디문제언어결과실행 시간메모리
981903michifiedPalembang Bridges (APIO15_bridge)C++17
22 / 100
46 ms4560 KiB
#include <bits/stdc++.h> #define ll long long using namespace std; ll ltot, rtot; priority_queue<int> pql; priority_queue<int, vector<int>, greater<int>> pqr; void put(ll x) { ll med = pql.empty() ? LLONG_MAX : pql.top(), tmp; if (x <= med) { pql.push(x); ltot += x; } else { pqr.push(x); rtot += x; } if (pqr.size() + 1 < pql.size()) { tmp = pql.top(); pql.pop(); pqr.push(tmp); ltot -= tmp; rtot += tmp; } else if (pqr.size() > pql.size()) { tmp = pqr.top(); pqr.pop(); pql.push(tmp); ltot += tmp; rtot -= tmp; } } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int k, n, i; cin >> k >> n; char az, bz; ll ap, bp, ss = 0, best = 0; vector<ll> pos; vector<pair<ll, ll>> ppl; for (i = 0; i < n; i++) { cin >> az >> ap >> bz >> bp; if (az == bz) ss += abs(ap - bp); else { if (ap > bp) swap(ap, bp); ppl.push_back({ap, bp}); ss++; } } n = ppl.size(); sort(ppl.begin(), ppl.end(), [](const pair<int, int>& one, const pair<int, int>& two){return one.first + one.second < two.first + two.second;}); ltot = rtot = 0; vector<ll> pref(n + 1); for (i = 0; i < n; i++) { put(ppl[i].first); put(ppl[i].second); pref[i + 1] = rtot - ltot; } best = pref[n]; if (k == 2) { while (not pql.empty()) pql.pop(); while (not pqr.empty()) pqr.pop(); ltot = rtot = 0; for (i = 0; i < n; i++) { put(ppl[i].first); put(ppl[i].second); best = min(best, rtot - ltot + pref[i]); } } cout << ss + best; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...