Submission #1094790

#TimeUsernameProblemLanguageResultExecution timeMemory
1094790DaciejMaciejPalembang Bridges (APIO15_bridge)C++17
100 / 100
65 ms5852 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> PII; typedef vector<pair<int, int>> VPII; typedef vector<long long> VL; #define PB push_back #define ALL(x) x.begin(), x.end() #define SPACE ' ' #define LINE '\n' priority_queue<int> lq; priority_queue<int, vector<int>, greater<int>> rq; ll lsum = 0, rsum = 0; void insert(int x) { if (lq.empty() || x <= lq.top()) { lq.push(x); lsum += x; } else { rq.push(x); rsum += x; } if (lq.size() > rq.size() + 1) { int tmp = lq.top(); lq.pop(); lsum -= tmp; rq.push(tmp); rsum += tmp; } else if (rq.size() > lq.size()) { int tmp = rq.top(); rq.pop(); rsum -= tmp; lq.push(tmp); lsum += tmp; } } void solve() { int n, k; cin >> k >> n; ll same = 0; VPII vec = {{0, 0}}; // Start with dummy element for (int i = 0; i < n; ++i) { char a, b; int x, y; cin >> a >> x >> b >> y; if (a == b) { same += abs(x - y); } else { vec.PB({x, y}); } } sort(ALL(vec), [](const PII &a, const PII &b) { return a.first + a.second < b.first + b.second; }); n = vec.size() - 1; VL pref(n + 1, 0); for (int i = 1; i <= n; ++i) { auto [x, y] = vec[i]; insert(x); insert(y); pref[i] = rsum - lsum; } ll ans = pref[n]; if (k == 2) { while (!lq.empty()) lq.pop(); while (!rq.empty()) rq.pop(); lsum = rsum = 0; for (int i = n; i >= 1; --i) { auto [x, y] = vec[i]; insert(x); insert(y); ans = min(ans, rsum - lsum + pref[i - 1]); } } cout << same + ans + n << LINE; } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int t = 1; // cin >> t; while (t--) solve(); }
#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...