제출 #1168668

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1168668		julia_08	Palembang Bridges (APIO15_bridge)	C++20	100 / 100	411 ms	11304 KiB

bridge

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

using ll = long long;

multiset<ll> ini_1, fim_1, ini_2, fim_2;

ll sum_ini_1, sum_fim_1, sum_ini_2, sum_fim_2;

void add_begin(int a){

  if(!ini_1.empty() && a > *ini_1.rbegin()){
    sum_fim_1 += a;
    fim_1.insert(a);

  } else{
    sum_ini_1 += a;
    ini_1.insert(a);
  }

  while(fim_1.size() < ini_1.size()){

    fim_1.insert(*ini_1.rbegin());
    sum_fim_1 += *ini_1.rbegin();

    sum_ini_1 -= *ini_1.rbegin();
    ini_1.erase(ini_1.find(*ini_1.rbegin()));

  }

  while(ini_1.size() < fim_1.size()){

    ini_1.insert(*fim_1.begin());
    sum_ini_1 += *fim_1.begin();

    sum_fim_1 -= *fim_1.begin();
    fim_1.erase(fim_1.begin());

  }

}

void remove_end(int a){

  if(ini_2.find(a) != ini_2.end()){
    sum_ini_2 -= a;
    ini_2.erase(ini_2.find(a));

  } else{
    sum_fim_2 -= a;
    fim_2.erase(fim_2.find(a));
  }

  while(fim_2.size() < ini_2.size()){

    fim_2.insert(*ini_2.rbegin());
    sum_fim_2 += *ini_2.rbegin();

    sum_ini_2 -= *ini_2.rbegin();
    ini_2.erase(ini_2.find(*ini_2.rbegin()));

  }

  while(ini_2.size() < fim_2.size()){

    ini_2.insert(*fim_2.begin());
    sum_ini_2 += *fim_2.begin();

    sum_fim_2 -= *fim_2.begin();
    fim_2.erase(fim_2.begin());

  }

}

ll solve(){

  ll left = 0, right = 0;

  if(!ini_1.empty()){
    int m_1 = *ini_1.rbegin();
    left = m_1 * ((int) ini_1.size()) - sum_ini_1 + sum_fim_1 - m_1 * ((int) fim_1.size());
  }

  if(!ini_2.empty()){
    int m_2 = *ini_2.rbegin();
    right = m_2 * ((int) ini_2.size()) - sum_ini_2 + sum_fim_2 - m_2 * ((int) fim_2.size());
  }

  return left + right;
}

int main(){
  cin.tie(0)->sync_with_stdio(0);

  int k, n; cin >> k >> n;

  ll x = 0;

  vector<int> a;
  vector<pair<int, int>> v;

  for(int i=1; i<=n; i++){

    char p, q; int s, t; cin >> p >> s >> q >> t;

    if(p == q){
      x += abs(s - t);

    } else{

      x ++;

      a.push_back(s), a.push_back(t);
      v.push_back({s + t, s});

    }

  }

  sort(a.begin(), a.end());
  sort(v.begin(), v.end());

  ll ans = 0;

  for(int i=0; i<a.size(); i++) ans += abs(a[i] - a[a.size() / 2]);

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

  for(int i=0; i<v.size(); i++){
    fim_2.insert(v[i].first - v[i].second);
    fim_2.insert(v[i].second);

    sum_fim_2 += v[i].first;
  }

  while(ini_2.size() < fim_2.size()){

    ini_2.insert(*fim_2.begin());
    sum_ini_2 += *fim_2.begin();

    sum_fim_2 -= *fim_2.begin();
    fim_2.erase(fim_2.begin());

  }

  for(int i=0; i<v.size(); i++){
    add_begin(v[i].first - v[i].second), add_begin(v[i].second);
    remove_end(v[i].first - v[i].second), remove_end(v[i].second);

    ans = min(ans, solve());
  }

  cout << ans + x << "\n";

  return 0;
}

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