Submission #643124

#	Time	Username	Problem	Language	Result	Execution time	Memory
643124		minase	Palembang Bridges (APIO15_bridge)	C++17	0 / 100	1 ms	332 KiB

bridge

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;

bool cmp(pair<int, int> a, pair<int, int> b) {
  return a.first + a.second < b.first + b.second;
}

priority_queue<int> lpq;
priority_queue<int, vector<int>, greater<int>> rpq;
i64 lsum, rsum;

void insert(int x) {
  int med = (lpq.size() ? lpq.top() : 1000000001);
  if (x <= med) {
    lpq.push(x);
    lsum += x;
  } else {
    rpq.push(x);
    rsum += x;
  }

  if (rpq.size() + 1 < lpq.size()) {
    int nxt = lpq.top();
    lpq.pop();
    rpq.push(nxt);
    lsum -= nxt;
    rsum += nxt;
  } else if (lpq.size() < rpq.size()) {
    int nxt = rpq.top();
    rpq.pop();
    lpq.push(nxt);
    rsum -= nxt;
    lsum += nxt;
  }
}

i64 pref[100001];

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);

  int n, k;
  i64 same_side = 0;
  vector<pair<int, int>> v{{0, 0}};
  cin >> k >> n;
  for (int i = 0; i < n; i++) {
    char a, b;
    int x, y;
    cin >> a >> b >> x >> y;
    if (a == b)
      same_side += abs(x - y);
    else
      v.push_back({x, y});
  }
  sort(v.begin(), v.end(), cmp);

  n = v.size() - 1;
  same_side += n;

  lsum = rsum = 0;
  for (int i = 1; i <= n; i++) {
    insert(v[i].first);
    insert(v[i].second);
    pref[i] = rsum - lsum;
  }

  i64 ans = pref[n];
  if (k == 2) {
    while (lpq.size())
      lpq.pop();
    while (rpq.size())
      rpq.pop();
    lsum = rsum = 0;

    for (int i = n; i; i--) {
      insert(v[i].first);
      insert(v[i].second);
      ans = min(ans, rsum - lsum + pref[i - 1]);
    }
  }
  cout << same_side + ans << '\n';
}

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