Submission #94470

#	Time	Username	Problem	Language	Result	Execution time	Memory
94470		wxh010910	Wiring (IOI17_wiring)	C++17	100 / 100	43 ms	9464 KiB

wiring

#include <bits/stdc++.h>
#include "wiring.h"

using namespace std;

long long min_total_length(vector<int> r, vector<int> b) {
  int n = r.size(), m = b.size();
  vector<pair<int, int>> all;
  for (int i = 0, j = 0; i < n; ++i) {
    while (j < m && b[j] < r[i]) {
      all.emplace_back(b[j++], 1);
    }
    all.emplace_back(r[i], -1);
    if (i == n - 1) {
      while (j < m) {
        all.emplace_back(b[j++], 1);
      }
    }
  }
  vector<int> pref(n + m + 1, -1);
  vector<long long> dp(n + m + 1);
  vector<long long> sum(n + m + 1);
  int cur = n;
  pref[cur] = 0;
  for (int i = 0, ptr_r = 0, ptr_b = 0; i < n + m; ++i) {
    sum[i + 1] = sum[i] + all[i].first * all[i].second;
    cur += all[i].second;
    if (all[i].second == -1) {
      while (ptr_b < m && b[ptr_b] < all[i].first) {
        ++ptr_b;
      }
      if (!ptr_b) {
        dp[i + 1] = dp[i] + b[ptr_b] - all[i].first;
      } else if (ptr_b == m) {
        dp[i + 1] = dp[i] + all[i].first - b[ptr_b - 1];
      } else {
        dp[i + 1] = dp[i] + min(b[ptr_b] - all[i].first, all[i].first - b[ptr_b - 1]);
      }
    } else {
      while (ptr_r < n && r[ptr_r] < all[i].first) {
        ++ptr_r;
      }
      if (!ptr_r) {
        dp[i + 1] = dp[i] + r[ptr_r] - all[i].first;
      } else if (ptr_r == n) {
        dp[i + 1] = dp[i] + all[i].first - r[ptr_r - 1];
      } else {
        dp[i + 1] = dp[i] + min(r[ptr_r] - all[i].first, all[i].first - r[ptr_r - 1]);
      }
    }
    if (pref[cur] != -1) {
      dp[i + 1] = min(dp[i + 1], dp[pref[cur]] + abs(sum[i + 1] - sum[pref[cur]]));
    }
    pref[cur] = i + 1;
  }
  return dp[n + m];
}

• Subtask 1: 7 / 7
• Subtask 2: 13 / 13
• Subtask 3: 10 / 10
• Subtask 4: 25 / 25
• Subtask 5: 45 / 45