Submission #1247208

#	Time	Username	Problem	Language	Result	Execution time	Memory
1247208		kunzaZa183	Wiring (IOI17_wiring)	C++20	100 / 100	40 ms	8116 KiB

wiring

#include "wiring.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

long long min_total_length(vector<int> r, vector<int> b) {
  vector<pair<int, int>> vpii;
  for (auto a : r)
    vpii.emplace_back(a, 0);
  for (auto a : b)
    vpii.emplace_back(a, 1);

  sort(vpii.begin(), vpii.end());

  vector<ll> qsum(vpii.size());
  qsum[0] = vpii[0].first;
  for (int i = 1; i < vpii.size(); i++)
    qsum[i] = qsum[i - 1] + vpii[i].first;

  auto qry = [&](int l, int r) {
    if (l == 0)
      return qsum[r];
    return qsum[r] - qsum[l - 1];
  };

  vector<ll> dp(vpii.size(), LLONG_MAX);
  auto matching = [&](int i1, int i2, int i3, int i4) {
    int n = (i2 - i1 + 1), m = (i4 - i3 + 1);

    ll bef;
    if (i1 == 0)
      bef = 0;
    else {
      bef = min(dp[i1 - 1], dp[i1]);
    }

    if (bef == LLONG_MAX)
      return LLONG_MAX;

    if (n < m) {
      ll k = m - n;
      return qry(i3, i4) - qry(i1, i2) - k * vpii[i2].first + bef;
    } else {
      ll k = n - m;
      return qry(i3, i4) - qry(i1, i2) + k * vpii[i3].first + bef;
    }
  };

  int in0 = 0, in1 = 0;
  for (int i = 0; i < vpii.size(); i++)
    if (vpii[i].second != vpii[0].second &&
        (i + 1 == vpii.size() || vpii[i].second != vpii[i + 1].second)) {
      in1 = i;
      break;
    }

  vector<array<int, 3>> vai3;
  vai3.push_back({vpii[0].second, 0, 0});
  for (int i = 1; i < vpii.size(); i++)
    if (vai3.back()[0] == vpii[i].second) {
      vai3.back()[2]++;
    } else {
      vai3.push_back({vpii[i].second, i, i});
    }

  // for (auto [a, b, c] : vai3) {
  //   cout << a << ' ' << b << ' ' << c << "\n";
  // }
  // cout << "\n";

  for (int i = 1; i < vai3.size(); i++) {
    int in0 = vai3[i - 1][2];
    for (int j = vai3[i][1]; j <= vai3[i][2]; j++) {
      while (in0 > vai3[i - 1][1] &&
             matching(in0 - 1, vai3[i - 1][2], vai3[i][1], j) <=
                 matching(in0, vai3[i - 1][2], vai3[i][1], j)) {
        in0--;
      }

      dp[j] = matching(in0, vai3[i - 1][2], vai3[i][1], j);
      // cout << in0 << " " << j << " " << dp[j] << "\n";
    }
  }

  return dp.back();
}

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