제출 #1028584

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1028584		vjudge1	Palembang Bridges (APIO15_bridge)	C++17	31 / 100	2098 ms	5564 KiB

bridge

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

int main()
{
  int k, n;
  cin >> k >> n;
  ll ans = 0;
  vector<pair<int,int> > p;
  for(int i = 0; i < n; i ++)
    {
      char P, Q;
      int s, t;
      cin >> P >> s >> Q >> t;
      if(t < s) swap(s, t);
      if(P == Q)
	ans += t - s;
      else
	p.push_back({s, t});
    }

  ans += p.size();
  
  if(k == 1)
    {
      vector<ll> v;
      for(auto [x, y] : p)
	{
	  v.push_back(x);
	  v.push_back(y);
	}
      
      sort(v.begin(), v.end());
      ll testans = 1e18 * (!v.empty()), suf = 0, sz = v.size();
      for(ll i : v) suf += i;
      ll prf = 0, cnt = 0;
      for(ll i : v)
	{
	  testans = min(testans, cnt * i - prf + suf - (sz - cnt) * i);
	  prf += i;
	  suf -= i;
	  cnt++;
	}
      
      ans += testans;
    }
  else
    {
      ll testans = 1e18 * (!p.empty());
      
      vector<ll> v;
      for(auto [x, y] : p)
	v.push_back(x), v.push_back(y);

      for(int i : v)
	for(int j : v)
	  {
	    ll temp = 0;
	    for(auto [x, y] : p)
	      {
		temp += min(abs(x - i) + abs(y - i), abs(x - j) + abs(y - j));
	      }
	    testans = min(testans, temp);
	  }
      ans += testans;
    }
  cout << ans << endl;
  return 0;
}

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