Submission #1225222

#	Time	Username	Problem	Language	Result	Execution time	Memory
1225222		kunzaZa183	Palembang Bridges (APIO15_bridge)	C++20	0 / 100	1 ms	328 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);
  });

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

  pref[0] = 0;
  priority_queue<int> pqi;
  ll sm = 0, sm2 = 0;
  ll ct2 = 0;

  auto ins = [&](int x) {
    pqi.push(x);
    sm += x;
    if (pqi.size() > ct2 + 1) {
      ct2++;
      sm2 += pqi.top();
      sm -= pqi.top();
      pqi.pop();
    }
  };

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

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

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

  pqi = priority_queue<int>();
  suf[vpii.size()] = 0;
  sm = sm2 = ct2 = 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 * ct2);
  }

  // cout << "VPII:\n";
  // for (auto a : vpii)
  //   cout << a.first << " " << a.second << "\n";
  // cout << "\n";
  //
  // for (auto a : pref)
  //   cout << a << " ";
  // cout << "\n";
  // 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: 0 / 8
• Subtask 2: 0 / 14
• Subtask 3: 0 / 9
• Subtask 4: 0 / 32
• Subtask 5: 0 / 37