Submission #137846

#	Time	Username	Problem	Language	Result	Execution time	Memory
137846		triplem5ds	Palembang Bridges (APIO15_bridge)	C++14	8 / 100	2029 ms	5764 KiB

bridge

///Let the game start
#pragma GCC optimize("Ofast,no-stack-protector")
#include "bits/stdc++.h"
using namespace std;
#define F first
#define S second
#define pb push_back
using ll = long long;
using ii = pair<int, int>;
using db = long double;
using ull = unsigned long long;
const int N = 3e5 + 5, MOD = 998244353;
const db EPS = 1e-7;
int A[N], B[N];
int main(){
#ifdef ONLINE_JUDGE
  ios_base::sync_with_stdio(0); cin.tie(0);
#endif // ONLINE_JUDGE
 
  int n, k;
  cin >> n >> k;  swap(k,n);
 
  ll ans = 0;
  char c1, c2;
  std::vector<ii> vp;
  for(int i = 0; i < n; i++){
    cin >> c1 >> A[i] >> c2 >> B[i];
    if(c1 == c2){
      ans += abs(A[i] - B[i]);
    } else {
      if(A[i] > B[i])swap(A[i], B[i]);
      vp.push_back(ii(A[i], B[i]));
    }
  }
 
  sort(vp.begin(), vp.end());
  n = vp.size();
  ans += n;
 
  if(k == 1){
 
    std::vector<int> cities;
 
    for(auto x : vp){
      cities.pb(x.F);
      cities.pb(x.S);
    }
 
    sort(cities.begin(), cities.end());
    cities.resize(unique(cities.begin(), cities.end()) - cities.begin());
    long long out = LLONG_MAX;
    if(vp.empty())out = 0;
    for(auto x : cities){
        long long val = 0;
        for(auto v : vp){
          if(v.second <= x){
            val += 2 * x - (v.first + v.second);
          } else if(v.first <= x){
            val += v.S - v.F;
          } else {
            val += (v.F + v.S) - 2 * x;
          }
        }
        out = min(out, val);
    }
    cout << ans + out << '\n';
 
  }
 
 
  return 0;
}

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