Submission #1094817

#TimeUsernameProblemLanguageResultExecution timeMemory
1094817Octa_pe_infoPalembang Bridges (APIO15_bridge)C++14
100 / 100
207 ms13640 KiB
#include <iostream> #include <set> #include <vector> #include <algorithm> using namespace std; multiset<int> st, dr; long long ssum = 0, dsum = 0; bool cmp(pair<int, int> a, pair<int, int> b) { return a.first + a.second < b.first + b.second; } void adauga(int nr) { int mid = st.empty() ? 10000001 : *st.rbegin(); if (nr <= mid) { st.insert(nr); ssum += nr; } else { dr.insert(nr); dsum += nr; } // Balancing the sets if (dr.size() + 1 < st.size()) { int auxs = *st.rbegin(); st.erase(st.find(auxs)); dr.insert(auxs); ssum -= auxs; dsum += auxs; } else if (st.size() < dr.size()) { int auxs = *dr.begin(); dr.erase(dr.find(auxs)); st.insert(auxs); dsum -= auxs; ssum += auxs; } } int main() { int n, k; cin >> k >> n; vector<pair<int, int>> poz; long long ans = 0, fel = 0; for (int i = 1; i <= n; i++) { int a, b; char c, cc; cin >> c >> a >> cc >> b; if (c == cc) fel += abs(a - b); // If both locations are on the same side else poz.push_back({a, b}); // If they are on opposite sides, add to the positions } // If no positions need a bridge, return early if (poz.empty()) { cout << fel << endl; return 0; } sort(poz.begin(), poz.end(), cmp); fel += poz.size(); // Counting the river crossings vector<long long> api(poz.size()); // First pass to compute differences for (int i = 0; i < poz.size(); i++) { adauga(poz[i].first); adauga(poz[i].second); api[i] = dsum - ssum; } ans = api[poz.size() - 1]; // The largest difference at the end if (k == 2) { // Clear the multisets for the second pass st.clear(); dr.clear(); ssum = dsum = 0; for (int i = poz.size() - 1; i >= 0; i--) { adauga(poz[i].first); adauga(poz[i].second); if (i > 0) { // Avoid accessing api[-1] ans = min(ans, dsum - ssum + api[i - 1]); } } } cout << ans + fel << endl; return 0; }

Compilation message (stderr)

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