제출 #1054428

#제출 시각아이디문제언어결과실행 시간메모리
1054428unnickPalembang Bridges (APIO15_bridge)C++14
100 / 100
73 ms4412 KiB
#include <iostream> #include <vector> #include <algorithm> #include <queue> using namespace std; typedef long long int ll; int main() { int k, n; cin >> k >> n; if (k != 1) { vector<pair<int, int> > a; ll sum = 0; for (int i = 0; i < n; i++) { char sa, sb; int ia, ib; cin >> sa >> ia >> sb >> ib; if (sa == sb) { sum += abs(ia-ib); continue; } a.push_back(make_pair(ia, ib)); sum += 1; } // if (a.size() == 1) { // cout << sum + abs(a[0].first - a[0].second) << "\n"; // } sort(a.begin(), a.end(), [](auto a, auto b){ return a.first + a.second < b.first + b.second; }); n = a.size(); vector<ll> lh_s(n+1); vector<ll> hh_s(n+1); // for (auto b : a) { // cout << b.first << " " << b.second << "\n"; // } for (int q = 0; q < 2; q++) { // cout << "== " << q << "\n"; if (q == 1) { for (int i = 0; i < a.size()/2; i++) { auto tmp = a[i]; a[i] = a[a.size()-i-1]; a[a.size()-i-1] = tmp; } } ll ls = 0, hs = 0; priority_queue<int> lh; priority_queue<int, vector<int>, greater<int> > hh; bool fst = true; int ptr = q == 0 ? 0 : a.size(); for (auto b : a) { // cout << "=" << ls << " " << hs << "\n"; if (q == 0) lh_s[ptr++] = hs - ls; else hh_s[ptr--] = hs - ls; if (fst) { lh.push(min(b.first, b.second)); hh.push(max(b.first, b.second)); ls = min(b.first, b.second); hs = max(b.first, b.second); fst = false; continue; } if (b.first > lh.top()) { hh.push(b.first); hs += b.first; } else { lh.push(b.first); ls += b.first; } if (b.second > lh.top()) { hh.push(b.second); hs += b.second; } else { lh.push(b.second); ls += b.second; } if (lh.size() > hh.size()) { int tmp = lh.top(); ls -= tmp; hs += tmp; lh.pop(); hh.push(tmp); } else if (lh.size() < hh.size()) { int tmp = hh.top(); hs -= tmp; ls += tmp; hh.pop(); lh.push(tmp); } // cout << b.first << " " << b.second << "\n"; } if (q == 0) lh_s[ptr] = hs - ls; else hh_s[ptr] = hs - ls; } // for (auto v : lh_s) { // cout << "l" << v << "\n"; // } // for (auto v : hh_s) { // cout << "h" << v << "\n"; // } ll bs = 0x7FFFFFFFFFFFFFFFLL; for (int i = 0; i < n+1; i++) { bs = min(bs, lh_s[i] + hh_s[i]); } sum += bs; cout << sum << "\n"; return 0; } vector<int> a; ll sum = 0; for (int i = 0; i < n; i++) { char sa, sb; int ia, ib; cin >> sa >> ia >> sb >> ib; if (sa == sb) { sum += abs(ia-ib); continue; } a.push_back(ia); a.push_back(ib); sum += 1; } sort(a.begin(), a.end()); int p = a[a.size() / 2]; for (auto v : a) { sum += abs(v-p); } cout << sum << "\n"; }

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

bridge.cpp: In function 'int main()':
bridge.cpp:48:35: 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 < a.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...