제출 #1005778

#제출 시각아이디문제언어결과실행 시간메모리
1005778a5a7Palembang Bridges (APIO15_bridge)C++14
22 / 100
2097 ms7336 KiB
#include <bits/stdc++.h> using namespace std; #include <ext/pb_ds/assoc_container.hpp> using namespace __gnu_pbds; template <class T> using indexedset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; typedef long long ll; int main(){ int k, n; cin >> k >> n; vector<pair<ll, ll>> deals; ll ans = 0; for (int i = 0; i < n; i++){ char a, b; ll c, d; cin >> a >> c >> b >> d; if (a == b) ans += max(d,c)-min(d,c); else deals.push_back({min(c,d), max(c,d)}); } ans += deals.size(); if (k == 1){ vector<ll> v; for (auto x : deals) v.push_back(x.first), v.push_back(x.second); sort(v.begin(), v.end()); ll med = v[v.size()/2]; for (ll x : v) ans += abs(x-med); }else{ sort(deals.begin(), deals.end(), [&](auto x, auto y){ return (x.first+x.second)<(y.first+y.second); }); multiset<ll> fh, fb, lh, lb; ll last = 0; ll first = 0; ll best = 1e9; for (int i = 0; i < (int) deals.size(); i++){ last += deals[i].first + deals[i].second; lh.insert(deals[i].first); lh.insert(deals[i].second); } while (lh.size() > lb.size()){ lb.insert(*lh.begin()); last -= 2 * (*lh.begin()); lh.erase(lh.begin()); } best = last; for (int i = 0; i < deals.size(); i++){ first += deals[i].second + deals[i].first; fh.insert(deals[i].first); fh.insert(deals[i].second); while (fh.size() > fb.size()){ fb.insert(*fh.begin()); first -= 2 * (*fh.begin()); fh.erase(fh.begin()); } if (lh.count(deals[i].first)) lh.erase(lh.find(deals[i].first)), last -= deals[i].first; else lb.erase(lb.find(deals[i].first)), last += deals[i].first; if (lh.count(deals[i].second)) lh.erase(lh.find(deals[i].second)), last -= deals[i].second; else lb.erase(lb.find(deals[i].second)), last += deals[i].second; while (lh.size() > lb.size()){ lb.insert(*lh.begin()); last -= 2 * (*lh.begin()); lh.erase(lh.begin()); } while (lh.size() < lb.size()){ ll number = *--lb.end(); lh.insert(number); last += 2 * number; lh.erase(lh.find(number)); } best = min(best, first+last); } ans += best; } cout << ans << endl; }

컴파일 시 표준 에러 (stderr) 메시지

bridge.cpp: In function 'int main()':
bridge.cpp:47:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |         for (int i = 0; i < deals.size(); i++){
      |                         ~~^~~~~~~~~~~~~~
#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...