Submission #60542

#	Time	Username	Problem	Language	Result	Execution time	Memory
60542		Flugan42	Palembang Bridges (APIO15_bridge)	C++14	22 / 100	174 ms	2836 KiB

bridge

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;

typedef long long ll;
typedef long double lld;
typedef vector<ll> vi;
typedef pair<ll,ll> ii;
typedef vector<ii> vii;

#define rep(i, from, to) for(int i = from; i < to; i++)
#define inf 1000000000000000000
#define sz(x) (ll)(x).size()

int main(){
  char a,b; ll n,c,d,k,s = 0,s1 = 0;
  cin >> k >> n;
  vi Q;
  rep(i, 0, n){
    cin >> a >> c >> b >> d;
    if (a == b) s += abs(d-c);
    else { Q.push_back(c); Q.push_back(d); }
  }
  sort(Q.begin(), Q.end());
  s += sz(Q)/2;
  if (sz(Q) == 0) { cout << s << endl; exit(0); }
  if (k == 1) rep(i, 0, sz(Q)) s += abs(Q[i]-Q[sz(Q)/2]);
  else {
    vi d1, d2;
    d1.assign(sz(Q), 0);
    d2.assign(sz(Q), 0);
    d1[0] = 0; d2.back() = 0;
    rep(i, 1, sz(Q)){
      d1[i] = d1[i-1]+Q[i]-Q[0];
      d2[sz(Q)-i-1] = d2[sz(Q)-i]+Q.back()-Q[sz(Q)-i-1];
    }
    s1 = inf;
    rep(i, 0, sz(Q)-1){
      ll temp = 0; ll b1 = i/2, b2 = (sz(Q)+i)/2;
      temp += d1[i]-d1[b1];
      temp -= (Q[b1]-Q[0])*(i-b1);
      temp += d1.back()-d1[b2];
      temp -= (Q[b2]-Q[0])*(sz(Q)-b2-1);

      temp += d2[0]-d2[b1];
      temp -= (Q.back()-Q[b1])*b1;
      temp += d2[i+1]-d2[b2];
      temp -= (Q.back()-Q[b2])*(b2-i-1);
      s1 = min(temp, s1);
    }
  }
  cout << s+s1 << endl;
}

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