Submission #121501

#	Time	Username	Problem	Language	Result	Execution time	Memory
121501		IOrtroiii	Palembang Bridges (APIO15_bridge)	C++14	22 / 100	419 ms	15448 KiB

bridge

/*
1 5
B 0 A 4
B 1 B 3
A 5 B 7
B 2 A 6
B 1 A 7
*/
#include <bits/stdc++.h>

using namespace std;

using ll = long long;

ll lsum;
ll rsum;
multiset<int> lval;
multiset<int> rval;

void add(int u, int v) {
   rsum += u;
   rval.insert(u);
   rsum += v;
   rval.insert(v);
   while (rval.size() > lval.size()) {
      int x = *rval.begin();
      rsum -= x;
      rval.erase(rval.find(x));
      lsum += x;
      lval.insert(x);
   }
   while (*--lval.end() > *rval.begin()) {
      int x = *--lval.end();
      int y = *rval.begin();
      lsum -= x;
      lval.erase(lval.find(x));
      lsum += y;
      lval.insert(y);
      rsum -= y;
      rval.erase(rval.find(y));
      rsum += x;
      rval.insert(x);
   }
}

vector<ll> eval(vector<pair<int, int>> vals) {
   lsum = 0;
   lval.clear();
   rsum = 0;
   rval.clear();
   int n = vals.size();
   vector<ll> f(1, 0);
   for (int i = 0; i < n; ++i) {
      add(vals[i].first, vals[i].second);
      f.push_back(rsum - lsum);
   }
   return f;
}

int main() {
   ios_base::sync_with_stdio(false);
   int k, n;
   cin >> k >> n;
   ll ans = 0;
   vector<pair<int, int>> vals;
   for (int i = 0; i < n; ++i) {
      string p, q;
      int s, t;
      cin >> p >> s >> q >> t;
      if (p == q) {
         ans += abs(s - t);
      } else {
         ++ans;
         vals.emplace_back(s, t);
      }
   }
   sort(vals.begin(), vals.end(), [&](pair<int, int> u, pair<int, int> v) {
      return u.first + u.second < v.first + v.second;
   });
   auto f = eval(vals);
   reverse(vals.begin(), vals.end());
   auto g = eval(vals);
   int m = vals.size();
   ll mn = 1e18;
   for (int i = 0; i < (k == 1 ? 1 : m); ++i) {
      mn = min(mn, f[i] + g[m - i]);
   }
   cout << ans + mn << "\n";
}

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