Submission #1225241

#	Time	Username	Problem	Language	Result	Execution time	Memory
1225241		kunzaZa183	Palembang Bridges (APIO15_bridge)	C++20	100 / 100	80 ms	4536 KiB

bridge

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
  int k, n;
  cin >> k >> n;
  ll ans = 0;
  vector<ll> vi;
  vector<pair<int, int>> vpii;
  for (int i = 0; i < n; i++) {
    char a, b;
    int x, y;
    cin >> a >> x >> b >> y;
    if (a == b) {
      ans += abs(y - x);
    } else {
      vpii.push_back(minmax(x, y));
      ans++;
    }
  }

  sort(vpii.begin(), vpii.end(), [&](pair<int, int> a, pair<int, int> b) {
    return (a.first + a.second) < (b.first + b.second);
  });

  // cout << "VPII:\n";
  // for (auto a : vpii)
  //   cout << a.first << " " << a.second << "\n";
  // cout << "\n";

  vector<ll> pref(vpii.size() + 1), suf(vpii.size() + 1);

  pref[0] = 0;
  priority_queue<int> pqi;
  priority_queue<int, vector<int>, greater<int>> pqi2;
  ll sm = 0, sm2 = 0;

  auto ins = [&](int x) {
    if (pqi.empty() || x > pqi.top()) {
      pqi2.push(x);
      sm2 += x;

      if (pqi2.size() > pqi.size()) {
        sm2 -= pqi2.top();
        sm += pqi2.top();
        pqi.push(pqi2.top());
        pqi2.pop();
      }
    } else {
      pqi.push(x);
      sm += x;

      if (pqi.size() > pqi2.size() + 1) {
        sm2 += pqi.top();
        sm -= pqi.top();
        pqi2.push(pqi.top());
        pqi.pop();
      }
    }
  };

  for (int i = 1; i <= vpii.size(); i++) {
    // cout << i << "\n";
    ins(vpii[i - 1].first), ins(vpii[i - 1].second);

    // cout << "PASS\n";
    ll x = pqi.top();
    pref[i] = (x * pqi.size() - sm) + (sm2 - x * pqi2.size());
  }

  // for (auto a : pref)
  //   cout << a << " ";
  // cout << "\n";

  if (k == 1) {
    cout << ans + pref.back() << "\n";
    return 0;
  }

  pqi = priority_queue<int>();
  pqi2 = priority_queue<int, vector<int>, greater<int>>();
  suf[vpii.size()] = 0;
  sm = sm2 = 0;
  for (int i = ((int)(vpii.size())) - 1; i >= 0; i--) {
    ins(vpii[i].first), ins(vpii[i].second);

    ll x = pqi.top();
    suf[i] = (x * pqi.size() - sm) + (sm2 - x * pqi2.size());
  }

  //
  // for (auto a : suf)
  //   cout << a << " ";
  // cout << "\n";

  ll minans = LLONG_MAX;
  for (int i = 0; i <= vpii.size(); i++) {
    minans = min(minans, ans + suf[i] + pref[i]);
  }
  cout << minans << "\n";
}

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