Submission #842991

#	Time	Username	Problem	Language	Result	Execution time	Memory
842991		tch1cherin	Palembang Bridges (APIO15_bridge)	C++17	17 / 100	2043 ms	3884 KiB

bridge

#include <bits/stdc++.h>
using namespace std;

int main() {
  int K, N;
  cin >> K >> N;
  vector<int> P(N), Q(N);
  vector<int> A, B;
  long long ans = 0, tot = LLONG_MAX;
  vector<int> D;
  for (int i = 0; i < N; i++) {
    char X, Y;
    cin >> X >> P[i] >> Y >> Q[i];
    if (X > Y) {
      swap(P[i], Q[i]);
    }
    D.push_back(P[i]);
    D.push_back(Q[i]);
    if (X == Y) {
      ans += abs(P[i] - Q[i]);
    } else {
      A.push_back(P[i]);
      B.push_back(Q[i]);
    }
  }
  P = A, Q = B;
  N = (int)P.size();
  if (K == 1) {
    for (int x : D) {
      long long res = 0;
      for (int i = 0; i < N; i++) {
        res += abs(P[i] - x) + abs(Q[i] - x) + 1;
      }
      tot = min(tot, ans + res);
    }
  } else {
    for (int x : D) {
      for (int y : D) {
        long long res = 0;
        for (int i = 0; i < N; i++) {
          res += min(abs(P[i] - x) + abs(Q[i] - x), abs(P[i] - y) + abs(Q[i] - y)) + 1; 
        }
        tot = min(tot, ans + res);
      }
    }
  }
  cout << tot << "\n";
}

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