제출 #700860

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
700860		Abrar_Al_Samit	Palembang Bridges (APIO15_bridge)	C++17	78 / 100	280 ms	13552 KiB

bridge

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

#define pii pair<int,int>

const long long INF = 1e18;
void PlayGround() {
  int k, n;
  cin>>k>>n;

  long long ans = 0;
  vector<pair<int,int>>bag;
  for(int i=0; i<n; ++i) {
    char p, q;
    int s, t;
    cin>>p>>s>>q>>t;
    if(s>t) swap(s, t);
    if(p==q) {
      ans += t - s;
    } else {
      bag.emplace_back(s, t);
    }
  }  

  int m = bag.size();
  ans += m;

  if(m==0) {
    cout<<ans<<'\n';
    return;
  }

  sort(bag.begin(), bag.end(), [&] (pii x, pii y) {
    return x.first+x.second<y.first+y.second;
  });

  long long pre[m];

  long long S1 = 0, S2 = 0;
  multiset<int>m1, m2;
  for(int i=0; i<m; ++i) {
    m1.insert(bag[i].first), m2.insert(bag[i].second);
    S1 += bag[i].first;
    S2 += bag[i].second;

    while(*prev(m1.end())>*m2.begin()) {
      S1 -= *prev(m1.end());
      S1 += *m2.begin();
      S2 -= *m2.begin();
      S2 += *prev(m1.end());

      m2.insert(*prev(m1.end()));
      m1.erase(prev(m1.end()));

      m1.insert(*m2.begin());
      m2.erase(m2.begin());
    }

    int med = *m2.begin();

    pre[i] = med * (i+1) - S1 + S2 - med * (i+1);
  }

  long long best = INF;
  S1 = S2 = 0;
  m1.clear(), m2.clear();
  for(int i=m-1; i>=0; --i) {
    m1.insert(bag[i].first), m2.insert(bag[i].second);
    S1 += bag[i].first;
    S2 += bag[i].second;

    while(*prev(m1.end())>*m2.begin()) {
      S1 -= *prev(m1.end());
      S1 += *m2.begin();
      S2 -= *m2.begin();
      S2 += *prev(m1.end());

      m2.insert(*prev(m1.end()));
      m1.erase(prev(m1.end()));

      m1.insert(*m2.begin());
      m2.erase(m2.begin());
    }

    long long med = *m2.begin();

    long long cur = med * (m-i) - S1 + S2 - med * (m-i);
    if(i) cur += pre[i-1];
    best = min(best, cur);
  }

  ans += best;
  cout<<ans<<'\n';
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  PlayGround();
  return 0;
}

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