제출 #853709

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
853709		NeroZein	Palembang Bridges (APIO15_bridge)	C++17	100 / 100	153 ms	14288 KiB

bridge

#include "bits/stdc++.h"
using namespace std;

#ifdef Nero
#include "Deb.h"
#else
#define deb(...)
#endif

multiset<int> lo, hi; 
long long sum1, sum2; 

void fix() {
  if (lo.size() > hi.size() + 1) {
    int tmp = *lo.rbegin();
    sum1 -= tmp;
    lo.erase(lo.find(tmp)); 
    sum2 += tmp; 
    hi.insert(tmp); 
  } 
  if (hi.size() > lo.size()) {
    int tmp = *hi.begin();
    sum2 -= tmp; 
    hi.erase(hi.find(tmp));
    sum1 += tmp; 
    lo.insert(tmp); 
  }
}

void ins(int x) {
  if (!lo.empty() && x >= *lo.rbegin()) {
    sum2 += x;
    hi.insert(x);
  } else {
    sum1 += x; 
    lo.insert(x); 
  }
  fix(); 
}

long long get() {
  int med = *lo.rbegin();
  int sz1 = lo.size(), sz2 = hi.size();
  long long ret = (long long) med * sz1 - sum1 + sum2 - (long long) med * sz2;
  return ret;
}

void clear() {
  lo.clear();
  hi.clear();
  sum1 = sum2 = 0; 
}

int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int k, n;
  cin >> k >> n;
  long long ans = 0; 
  vector<pair<int,int>> vec; 
  for (int i = 0; i < n; ++i) {
    char z, z2;
    int x, x2;
    cin >> z >> x >> z2 >> x2;
    //if (x > x2) swap(x, x2); important for proof only
    if (z == z2) {
      ans += abs(x - x2); 
    } else {
      vec.emplace_back(x, x2); 
    }
  }
  if (!vec.size()) {
    cout << ans << '\n';
    return 0; 
  }
  n = vec.size();
  ans += n; 
  sort(vec.begin(), vec.end(), [](pair<int, int> i, pair<int, int> j) {
    return i.first + i.second < j.first + j.second; 
  });
  deb(vec); cout << '\n';
  vector<long long> pref(n); 
  for (int i = 0; i < n; ++i) {
    ins(vec[i].first);
    ins(vec[i].second);
    pref[i] = get(); 
  }
  clear(); 
  vector<long long> suf(n);
  for (int i = n - 1; i >= 0; --i) {
    ins(vec[i].first);
    ins(vec[i].second);
    suf[i] = get(); 
  }
  long long res = ans + pref.back();
  if (k == 2) {
    for (int i = 0; i < n - 1; ++i) {
      res = min(res, ans + pref[i] + suf[i + 1]); 
    }
  }
  cout << res << '\n'; 
  return 0;
}

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