제출 #970975

#제출 시각아이디문제언어결과실행 시간메모리
970975njoopPalembang Bridges (APIO15_bridge)C++14
22 / 100
101 ms11376 KiB
#include <bits/stdc++.h> #define ll long long using namespace std; int n, k, in1, in2, mxl, mnr; char c1, c2; vector<pair<int, int>> v; multiset<int> s1, s2; ll pref[100010], suff[100010], su1, su2, res, ans; bool cmp(const pair<int, int> &a, const pair<int, int> &b) { return a.first+a.second < b.first+b.second; } void insertVal(int in) { if(s1.size() <= s2.size()) { s1.insert(in); su1 += in; } else { s2.insert(in); su2 += in; } if(s1.size() && s2.size() && *s1.rbegin() > *s2.begin()) { mxl = *s1.rbegin(); mnr = *s2.begin(); su1 += mnr - mxl; su2 += mxl - mnr; s1.insert(mnr); s1.erase(s1.find(mxl)); s2.insert(mxl); s2.erase(s2.find(mnr)); } } int main() { cin.tie(0)->sync_with_stdio(0); cin >> k >> n; for(int i=0; i<n; i++) { cin >> c1 >> in1 >> c2 >> in2; if(c1 == c2) { res += abs(in1 - in2); continue; } v.push_back({in1, in2}); } sort(v.begin(), v.end(), cmp); res += v.size(); for(int i=0; i<v.size(); i++) { insertVal(v[i].first); insertVal(v[i].second); pref[i] = (s1.size()-s2.size())*(*s1.rbegin()) - su1 + su2; } ans = pref[v.size()-1]; if(k == 1) { cout << ans+res; return 0; } s1.clear(); s2.clear(); su1 = 0; su2 = 0; for(int i=v.size()-1; i>0; i--) { insertVal(v[i].first); insertVal(v[i].second); suff[i] = (s1.size()-s2.size())*(*s1.rbegin()) - su1 + su2; } for(int i=0; i<v.size()-2; i++) { ans = min(ans, pref[i]+suff[i+1]); } cout << ans+res; return 0; }

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

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