Submission #642218

#	Time	Username	Problem	Language	Result	Execution time	Memory
642218		kith14	Palembang Bridges (APIO15_bridge)	C++17	22 / 100	74 ms	5224 KiB

bridge

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

#define ll long long
#define db double
#define pairll pair<ll,ll>
#define lpairll pair<ll,pairll>

#define repp(i,a,b) for (ll i = a; i <= b; i++)
#define repz(i,a,b) for (ll i = a; i < b; i++)
#define repm(i,a,b) for (ll i = a; i >= b; i--)
#define fr first
#define sc second
#define mp make_pair
#define pb push_back

const ll N = 1e5+5, MOD = 1e9+7, M = 1e5+5;
ll tc = 1, n, m, sf[N], pr[N], R, L;
ll x, y, k, otsum, dg, dsum, idx;
string s, s1, s2, ye = "YES", no = "NO";
pairll ar[N];

priority_queue<ll> le;
priority_queue<ll,vector<ll>,greater<ll> > ri;

bool cmp(pairll a, pairll b){
  return(a.fr+a.sc < b.fr+b.sc);
}

void add(ll val){
  if (le.empty() || le.top() >= val) le.push(val), L += val;
  else ri.push(val), R += val;

  ll ls = le.size(), rs = ri.size();
  //move from left to right
  if (ls-rs >= 2){
    ll tt = le.top();
    le.pop();
    ri.push(tt);
    L -= tt;
    R += tt;
  }
  //move from right to left
  else if (rs > ls){
    ll tt = ri.top();
    ri.pop();
    le.push(tt);
    L += tt;
    R -= tt;
  }
}

void input(){
  cin >> k >> n;
  repp(i,1,n){
    char A, B;
    ll L, R;
    cin >> A >> L >> B >> R;
    if (L > R) swap(L,R);
    if (A == B) otsum += R-L;
    else{
      otsum++;
      idx++;
      ar[idx] = mp(L,R);
    }
  }
}

void solve(){
  sort(ar+1,ar+idx+1,cmp);
  //build prefix
  L = R = 0;
  repp(i,1,idx){
    add(ar[i].fr);
    add(ar[i].sc);
    pr[i] = R-L;
  }

  //build suffix
  while(le.size()) le.pop();
  while(ri.size()) ri.pop();
  L = R = 0;
  repm(i,idx,1){
    add(ar[i].fr);
    add(ar[i].sc);
    sf[i] = R-L;
  }
  ll ans = LLONG_MAX;
  if (k == 1) ans = pr[idx];
  else{
    repp(i,1,idx){
      ans = min(ans,pr[i]+sf[i+1]);
    }
  }
  cout << ans+otsum << endl;
}

int main(){
  ios_base::sync_with_stdio(0);
  cin.tie(NULL);
  cout.tie(NULL);
  //cin >> tc;
  while(tc--){
    input();
    solve();
  }
}

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