Submission #628124

#	Time	Username	Problem	Language	Result	Execution time	Memory
628124		kalash04	Palembang Bridges (APIO15_bridge)	C++17	0 / 100	1 ms	468 KiB

bridge

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
#define int long long int
ll MOD = 1e9 + 7;

priority_queue<int, vector<int>, greater<int>> min_heap;
priority_queue<int> max_heap;
int mx, mn;

void insert(int x) {
  int median = (max_heap.size() ? max_heap.top() : 1e9 + 1);
  if(x <= median) max_heap.push(x), mx += x;
  else min_heap.push(x), mn += x;
  if(min_heap.size() + 1 < max_heap.size()) {
    int change = max_heap.top();
    mx -= change;
    mn += change;
    max_heap.pop();
    min_heap.push(change);
  } else if(max_heap.size() < min_heap.size()) {
    int change = min_heap.top();
    mn -= change;
    mx += change;
    min_heap.pop();
    max_heap.push(change);
  }
}

void solve() {
  int k, n;
  cin >> k >> n;
  int dist = 0;
  vector<pair<int, int>> v;
  for(int i = 0; i < n; i++) {
    char a, b; int c, d;
    cin >> a >> c >> b >> d;
    if(a == b) dist += abs(c - d);
    else v.push_back({c, d});
  }
  sort(v.begin(), v.end(), [](auto const& a, auto const& b) {
    return a.first + a.second < b.first + b.second;
  });
  dist += v.size();
  n = v.size();
  mx = mn = 0;
  vector<int> prefix(n);
  for(int i = 0; i < n; i++) {
    insert(v[i].first);
    insert(v[i].second);
    prefix[i] += mn - mx;
  }
  int ans = prefix[n - 1];
  if(k == 2) {
    while(max_heap.size()) max_heap.pop();
    while(min_heap.size()) min_heap.pop();
    mx = mn = 0;
    for(int i = n - 1; i >= 0; i--) {
      insert(v[i].first);
      insert(v[i].second);
      ans = min(ans, (i != 0 ? prefix[i - 1] : 0) + mn - mx);
    }
  }
  cout << dist + ans << endl;
}

int32_t main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
  cout.tie(NULL);
	solve();
}

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