Submission #60545

#	Time	Username	Problem	Language	Result	Execution time	Memory
60545		dukati8	Palembang Bridges (APIO15_bridge)	C++14	0 / 100	3 ms	564 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(int i) {
  long long point=points[i];
  long long ans=0;
  for (auto a:travels) {
    long long c,d;
    c=a.first;
    d=a.second;
    if (point >d) ans+=2*(point-d);
    if (point<c) ans+=2*(c-point);
  }
  return ans;
}

int main() {
  unordered_set<long long> unip;
  int k,n;
  cin >> k >> n;
  long long sum=0;
  rep(i,0,n) {
    string 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+abs(c-d);
      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+50<hi) {
      int mid1=lo+(hi-lo)/3;
      int mid2=lo+(2*hi-2*lo)/3;
      long long val1,val2;
      val1=cost(mid1);
      val2=cost(mid2);
      if (val1<val2) hi=mid2;
      else lo=mid1;
    }
    long long best=1000000000000000;
    rep (i,lo,hi+1) {
      best=min(best,cost(i));
    }
    cout << best+sum << endl;
  }



}

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