제출 #60605

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
60605		dukati8	Palembang Bridges (APIO15_bridge)	C++14	22 / 100	335 ms	13328 KiB

bridge

#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for (int i=a; i<int(b); i++)
#define all(x) x.begin(),x.end()
vector <pair<long long,long long> > travels;
vector <long long> points;
long long cost(long long point){
  long long ans=0;
  for (auto a:travels) {
    long long c,d;
    c=a.first;
    d=a.second;
    ans+=abs(point-c) + abs(point-d);
  }
  return ans;
}

int main() {
  unordered_set<long long> unip;
  int k,n;
  cin >> k >> n;
  long long sum=0;
  rep(i,0,n) {
    char a,b;
    long long c,d;
    cin >> a >> c >> b >> d;
    if (a==b) {
      sum+=abs(c-d);
    }
    else {
      travels.push_back(make_pair(min(c,d),max(c,d)));
      sum+=1;
      unip.insert(c);
      unip.insert(d);
    }
  }
  for (auto x:unip) {
    points.push_back(x);
  }
  if (k==1) {
    sort(all(points));
    int lo,hi;
    lo=0;
    hi=points.size()-1;
    while (lo+2<hi) {
      int mid1=lo+(hi-lo)/3;
      int mid2=lo+(2*hi-2*lo)/3;
      long long val1,val2;
      val1=cost(points[mid1]);
      val2=cost(points[mid2]);
      if (val1<val2) hi=mid2;
      else lo=mid1;
    }
    long long best=1000000000000000;
    rep (i,lo,hi+1) {
      best=min(best,cost(points[i]));
    }
    if (best==1000000000000000) best=0;
    cout << best+sum << endl;
  }



}

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