제출 #497870

#제출 시각아이디문제언어결과실행 시간메모리
497870clamsPalembang Bridges (APIO15_bridge)C++17
22 / 100
116 ms13488 KiB
#include <bits/stdc++.h> using namespace std; #define int long long const int INF = 1e18; int sumlow = 0, sumhigh = 0; multiset<int> low, high; void sinsert(int val) { int med = low.empty() ? INF : *low.rbegin(); if (val > med) { high.insert(val); sumhigh += val; } else { low.insert(val); sumlow += val; } if (high.size() > low.size()) { int tmp = *high.begin(); low.insert(tmp); sumlow += tmp; sumhigh -= tmp; high.erase(high.find(tmp)); } else if (low.size() > high.size() + 1) { int tmp = *low.rbegin(); high.insert(tmp); sumhigh += tmp; sumlow -= tmp; low.erase(low.find(tmp)); } } signed main() { ios::sync_with_stdio(0); cin.tie(0); int k, n; cin >> k >> n; vector<pair<int, int>> diff; int same = 0; for (int i = 0; i < n; i++) { char p, q; int s, t; cin >> p >> s >> q >> t; if (p == q) { same += abs(s - t); } else { if (s > t) swap(s, t); diff.push_back({s, t}); } } sort(diff.begin(), diff.end(), [](const pair<int, int>& a, const pair<int, int>& b) { return a.first + a.second < b.first + b.second; }); int sz = diff.size(); same += sz; // crossing the river if (k == 1) { if (sz == 0) { cout << same; return 0; } for (int i = 0; i < sz; i++) { sinsert(diff[i].first); sinsert(diff[i].second); } int med = *low.rbegin(); int ans = (med * (int)low.size() - sumlow) + (sumhigh - med * (int)high.size()); cout << same + ans; return 0; } } /* 1 5 B 0 A 4 B 1 B 3 A 5 B 7 B 2 A 6 B 1 A 7 2 5 B 0 A 4 B 1 B 3 A 5 B 7 B 2 A 6 B 1 A 7 */
#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...