제출 #469834

#제출 시각아이디문제언어결과실행 시간메모리
469834training4usacoPalembang Bridges (APIO15_bridge)C++11
0 / 100
2 ms332 KiB
#include <iostream> #include <vector> #include <set> #include <algorithm> using namespace std; #define INF 1000000009 multiset<int> upper; multiset<int> lower; int lsum, usum; void build(int val) { int median; if(lower.empty()) { median = INF; } else{ median = *lower.rbegin(); } if (val <= median) { lower.insert(val); lsum += val; } else { upper.insert(val); usum += val; } if (upper.size() + 1 < lower.size()) { int moved = *lower.rbegin(); lower.erase(lower.find(moved)); upper.insert(moved); lsum -= moved; usum += moved; } else if (lower.size() < upper.size()) { int moved = *upper.begin(); upper.erase(upper.find(moved)); lower.insert(moved); usum -= moved; lsum += moved; } } bool comp(pair<int, int> a, pair<int, int> b) { return a.first + a.second < b.first + b.second; } vector<int> pref_sum; int main() { int n, k; cin >> k >> n; pref_sum = vector<int>(n + 1); vector<pair<int, int>> locs; locs.push_back({0, 0}); int same = 0; for(int i = 0; i < n; ++i) { char a, b; int c, d; cin >> a >> c >> b >> d; if(a == b) { same += abs(c - d); } else { locs.push_back({c, d}); } } sort(locs.begin(), locs.end(), comp); int new_n = locs.size() - 1; same += new_n; for(int i = 1; i <= new_n; ++i) { build(locs[i].first); build(locs[i].second); pref_sum[i] = usum - lsum; } int ans = pref_sum[new_n]; if (k == 2) { lower.clear(); upper.clear(); lsum = 0; usum = 0; for (int i = new_n; i > 0; i--) { build(locs[i].first); build(locs[i].second); ans = min(ans, usum - lsum + pref_sum[i - 1]); } } cout << same + ans << endl; 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...