Submission #964794

#	Time	Username	Problem	Language	Result	Execution time	Memory
964794		Soumya1	Palembang Bridges (APIO15_bridge)	C++17	100 / 100	210 ms	15272 KiB

bridge

#include <bits/stdc++.h>
using namespace std;
vector<long long> get(vector<pair<int, int>> v) {
  int n = v.size();
  multiset<int> l, r;
  vector<long long> p(n);
  long long suml = 0, sumr = 0;
  auto insert = [&](int x) {
    r.insert(x);
    sumr += x;
    if (!l.empty() && *prev(l.end()) > *r.begin()) {
      sumr += *prev(l.end());
      suml -= *prev(l.end());
      r.insert(*prev(l.end()));
      l.erase(prev(l.end()));
      sumr -= *r.begin();
      suml += *r.begin();
      l.insert(*r.begin());
      r.erase(r.begin());
    }
    if (l.size() < r.size()) {
      sumr -= *r.begin();
      suml += *r.begin();
      l.insert(*r.begin());
      r.erase(r.begin());
    }
  };
  for (int i = 0; i < n; i++) {
    insert(v[i].first);
    insert(v[i].second);
    int median = *prev(l.end());
    p[i] = 1LL * l.size() * median - suml + sumr - 1LL * r.size() * median;
  }
  return p;
}
void testCase() {
  int k, n;
  cin >> k >> n;
  vector<pair<int, int>> v;
  long long ans = 0;
  for (int i = 0; i < n; i++) {
    int x1, x2;
    char t1, t2;
    cin >> t1 >> x1 >> t2 >> x2;
    if (t1 == t2) ans += abs(x1 - x2);
    else ans++, v.push_back({min(x1, x2), max(x1, x2)});
  }
  sort(v.begin(), v.end(), [&](pair<int, int> i, pair<int, int> j) { return i.first + i.second < j.first + j.second; });
  if (v.empty()) {
    cout << ans << "\n";
    return;
  }
  auto p = get(v);
  reverse(v.begin(), v.end());
  auto s = get(v);
  reverse(s.begin(), s.end());
  if (k == 1) {
    cout << ans + p.back() << "\n";
    return;
  }
  long long mn = min(p.back(), s[0]);
  for (int i = 1; i < v.size(); i++) {
    mn = min(mn, p[i - 1] + s[i]);
  }
  cout << ans + mn << "\n";
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  testCase();
  return 0;
}

Compilation message (stderr)

bridge.cpp: In function 'void testCase()':
bridge.cpp:62:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |   for (int i = 1; i < v.size(); i++) {
      |                   ~~^~~~~~~~~~

• Subtask 1: 8 / 8
• Subtask 2: 14 / 14
• Subtask 3: 9 / 9
• Subtask 4: 32 / 32
• Subtask 5: 37 / 37