Submission #60588

#	Time	Username	Problem	Language	Result	Execution time	Memory
60588		dukati8	Palembang Bridges (APIO15_bridge)	C++14	8 / 100	2027 ms	3920 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;

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);
    ans += abs(point-d);
    ans += 1;
    /*assert (c<=d);
    ans+=abs(d-c);
    ans++;
    if (point >d) ans+=2*(point-d);
    if (point<c) ans+=2*(c-point);
    */
  }
  return ans;
}

int main() {
  int n,k;
  cin >> k >> n;
  long long sum=0;
  vector<long long> points;
  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(c,d));
      points.push_back(c);
      points.push_back(d);
    }
  }
  long long best=1000000000000000;
  rep (i,0,points.size()) {
    best=min(best,cost(points[i]));
  }
  if (best == 1000000000000000) best=0;
  cout << best+sum << endl;

}

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