Submission #1028568

#	Time	Username	Problem	Language	Result	Execution time	Memory
1028568		vjudge1	Palembang Bridges (APIO15_bridge)	C++17	0 / 100	0 ms	600 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});
    }

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

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