Submission #484514

#	Time	Username	Problem	Language	Result	Execution time	Memory
484514		MilosMilutinovic	Wiring (IOI17_wiring)	C++14	13 / 100	51 ms	14744 KiB

wiring

/**
 *    author: m371
 *    created: 03.11.2021 23:07:51
**/
#include <bits/stdc++.h>

using namespace std;

long long min_total_length(vector<int> r, vector<int> b) {
  int n = r.size() + b.size();
  vector<pair<int, int>> a;
  for (int i = 0; i < (int) r.size(); i++) {
    a.emplace_back(r[i], 0);
  }
  for (int i = 0; i < (int) b.size(); i++) {
    a.emplace_back(b[i], 1);
  }
  sort(a.begin(), a.end());
  vector<pair<int, int>> segs;
  for (int i = 0; i < n; i++) {
    int ptr = i;
    while (ptr + 1 < n && a[i].second == a[ptr + 1].second) {
      ptr += 1;
    }
    segs.emplace_back(i, ptr);
    i = ptr;
  }
  int sz = segs.size();
  vector<long long> dp(n);
  vector<vector<long long>> pref(sz);
  vector<vector<long long>> suff(sz);
  for (int i = 0; i < sz; i++) {
    int l = segs[i].first;
    int r = segs[i].second;
    int len = r - l + 1;
    vector<long long> aux(len);
    for (int j = len - 1; j >= 0; j--) {
      if (j + 1 < len) {
        aux[j] = aux[j + 1];
      }
      aux[j] += a[r].first - a[l + j].first;
    }
    long long sum = 0;
    const long long inf = (long long) 1e17;
    for (int j = 0; j < len; j++) { 
      sum += (a[l + j].first - a[l].first);
      if (i == 0) {
        dp[j + l] = inf;
      } else {
        int prv_sz = suff[i - 1].size();
        dp[j + l] = inf;
        dp[j + l] = min(dp[j + l], suff[i - 1][prv_sz - min(prv_sz, j + 1)] + sum + (j + 1) * 1LL * (a[l].first - a[l - 1].first));
        if (prv_sz > j + 1) {
          dp[j + l] = min(dp[j + l], pref[i - 1][prv_sz - j - 2] + sum);    
        } 
      }
    }
    if (i + 1 == sz) {
      continue;
    }
    pref[i].resize(len);
    suff[i].resize(len);  
    for (int j = 0; j < len; j++) {
      pref[i][j] = aux[j] + (l + j > 0 ? dp[l + j - 1] : 0LL) + (len - j) * 1LL * (a[r + 1].first - a[r].first);
      if (j > 0) {
        pref[i][j] = min(pref[i][j], pref[i][j - 1]);
      }
    }
    for (int j = len - 1; j >= 0; j--) {
      suff[i][j] = aux[j] + (l + j > 0 ? dp[l + j - 1] : 0LL);
      if (j + 1 < len) {
        suff[i][j] = min(suff[i][j], suff[i][j + 1]);
      }
    }
  }
  return dp[n - 1];
}

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