Submission #810721

#	Time	Username	Problem	Language	Result	Execution time	Memory
810721		erray	Wiring (IOI17_wiring)	C++17	100 / 100	39 ms	8468 KiB

wiring

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

using namespace std;
 
#ifdef DEBUG
  #include "/home/ioi/codes/debug.h"
#else
  #define debug(...) (void) 37
#endif


long long min_total_length(std::vector<int> r, std::vector<int> b) {
  vector<vector<int>> gs;
  {
    vector<int> m;
    merge(r.begin(), r.end(), b.begin(), b.end(), back_inserter(m));
    int pr = -1, pb = -1;
    int last = -1;
    for (int i = 0; i < int(m.size()); ++i) {
      int next = -1;
      if (pr + 1 < int(r.size()) && r[pr + 1] == m[i]) {
        ++pr;
        next = 0;
      } else {
        ++pb;
        next = 1;
      }
      if (next != last) {
        gs.push_back({});
      }
      gs.back().push_back(m[i]);
      swap(next, last);
    }
  }
  debug(gs);
  const long long inf = (long long) 1e17;
  vector<long long> dp(int(gs[0].size()) + 1, inf);
  dp[0] = 0;
  for (int bi = 1; bi < int(gs.size()); ++bi) {
    debug(dp);
    auto& v = gs[bi];
    auto& prev = gs[bi - 1];
    int n = int(v.size());
    int m = int(prev.size());
    int gap = v[0] - prev.back();
    vector<long long> small(n + 1, inf), big(n + 1, inf);
    {
      long long sum = 0;
      for (int i = m - 1; i >= 0; --i) {
        sum += prev[m - 1] - prev[i];
        int match = m - i;
        long long cost = sum + dp[i];
        if (match <= n) {
          big[match] = min(big[match], cost);
        }
        match = min(match, n);
        small[match] = min(small[match], cost + 1LL * (m - i) * gap);
      }
    }
    vector<long long> new_dp(n + 1);
    {
      long long mn = inf;
      for (int i = 1; i <= n; ++i) {
        mn = min(mn, big[i]);
        new_dp[i] = mn + 1LL * i * gap;
      }
    }
    {
      long long mn = inf;
      for (int i = n; i >= 1; --i) {
        mn = min(mn, small[i]);
        new_dp[i] = min(new_dp[i], mn);
      }
    }
    new_dp[0] = dp[m];
    {
      long long sum = 0;
      for (int i = 1; i <= n; ++i) {
        sum += v[i - 1] - v[0];
        new_dp[i] += sum;
      }
    }
    swap(dp, new_dp);
    for (int i = n; i > 0; --i) {
      dp[i - 1] = min(dp[i], dp[i - 1]);
    }
  }
  debug(dp);
  return dp.back();
}

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