Submission #430134

#	Time	Username	Problem	Language	Result	Execution time	Memory
430134		rama_pang	Coin Collecting (JOI19_ho_t4)	C++17	100 / 100	70 ms	1868 KiB

joi2019_ho_t4

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

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);

  int N;
  cin >> N;
  long long ans = 0;
  vector<vector<int>> need(3, vector<int>(N + 1));
  for (int i = 1; i <= 2; i++) {
    for (int j = 1; j <= N; j++) {
      need[i][j] = -1;
    }
  }
  for (int i = 0; i < 2 * N; i++) {
    int x, y;
    cin >> x >> y;
    if (x < 1) ans += 1 - x;
    if (x > N) ans += x - N;
    x = clamp(x, 1, N);
    if (y < 1) ans += 1 - y;
    if (y > 2) ans += y - 2;
    y = clamp(y, 1, 2);
    need[y][x] += 1;
  }

  vector<int> flow(3);
  for (int p = 1; p <= N; p++) {
    flow[1] += need[1][p];
    flow[2] += need[2][p];
    if (flow[1] < 0 && flow[2] > 0) {
      swap(flow[1], flow[2]);
      swap(need[1], need[2]);
    }
    if (flow[1] > 0 && flow[2] < 0) {
      int f = min(abs(flow[1]), abs(flow[2]));
      flow[1] -= f;
      flow[2] += f;
      ans += f;
    }
    ans += abs(flow[1]);
    ans += abs(flow[2]);
  }

  assert(flow[1] == 0 && flow[2] == 0);
  cout << ans << '\n';
  return 0;
}

• Subtask 1: 8 / 8
• Subtask 2: 29 / 29
• Subtask 3: 63 / 63