제출 #1126558

#제출 시각아이디문제언어결과실행 시간메모리
1126558ssitaramPalembang Bridges (APIO15_bridge)C++20
0 / 100
1 ms324 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; struct med { ll as, bs; priority_queue<int> a; priority_queue<int, vector<int>, greater<int>> b; med() : as(0), bs(0) {} void resz() { while (a.size() >= b.size() + 2) { int e = a.top(); as -= e; a.pop(); b.push(e); bs += e; } while (a.size() < b.size()) { int e = b.top(); bs -= e; b.pop(); a.push(e); as += e; } } void add(int v) { if (a.empty() || v < a.top()) { a.push(v); as += v; } else { b.push(v); bs += v; } resz(); } ll ans() { return (a.top() * a.size()) - as + bs - (a.top() * b.size()); } }; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int k, n; cin >> k >> n; ll ans = 0; vector<vector<int>> route = {{}}; for (int i = 0; i < n; ++i) { char ac, bc; int a, b; cin >> ac >> a >> bc >> b; if (ac == bc) { ans += b - a; } else { route.push_back({a + b, a, b}); } } n = route.size() - 1; if (n == 0) { cout << ans << '\n'; return 0; } route.push_back({}); sort(next(route.begin()), prev(prev(route.end()))); vector<ll> pref(n + 1); pref[0] = 0; med m1; for (int i = 1; i <= n; ++i) { m1.add(route[i][1]); m1.add(route[i][2]); pref[i] = m1.ans(); } vector<ll> suff(n + 2); suff[n + 1] = 0; med m2; for (int i = n; i >= 1; --i) { m2.add(route[i][1]); m2.add(route[i][2]); suff[i] = m2.ans(); } if (k == 1) { cout << pref[n] + ans + n << '\n'; } else { ll best = INT64_MAX; for (int i = 0; i <= n; ++i) { best = min(best, pref[i] + suff[i + 1]); } cout << best + ans + n << '\n'; } 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...