Submission #831473

#	Time	Username	Problem	Language	Result	Execution time	Memory
831473		WLZ	Wiring (IOI17_wiring)	C++17	17 / 100	1093 ms	8124 KiB

wiring

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

using ll = long long;

const ll LINF = (ll) 1e18;

long long min_total_length(std::vector<int> a, std::vector<int> b) {
  int n = (int) a.size(), m = (int) b.size();
  vector< pair<int, int> > v;
  for (int i = 0; i < n; i++) v.emplace_back(a[i], 0);
  for (int i = 0; i < m; i++) v.emplace_back(b[i], 1);
  sort(v.begin(), v.end());
  v.insert(v.begin(), {0, -1});
  vector<int> seg(n + m + 1); seg[1] = 0; seg[0] = -5;
  vector<int> sz;
  int len = 1;
  for (int i = 2; i <= n + m; i++) {
    seg[i] = seg[i - 1];
    len++;
    if (v[i].second != v[i - 1].second) {
      sz.push_back(len - 1);
      seg[i]++, len = 1;
    }
  }
  sz.push_back(len);
  vector<ll> dp(n + m + 1, LINF); dp[0] = 0;
  for (int i = 1; i <= n + m; i++) {
    if (seg[i] == 0) continue;
    int cnt_l = 0, cnt_r = 0;
    ll sum_l = 0, sum_r = 0;
    ll last_l = 0, last_r = -1;
    for (int j = i - 1; j >= 0; j--) {
      if (seg[j + 1] == seg[i]) {
        cnt_l++; sum_l += v[j + 1].first;
        last_l = v[j + 1].first;
      }
      if (seg[j + 1] == seg[i] - 1) {
        cnt_r++; sum_r += v[j + 1].first;
        if (last_r == -1) last_r = v[j + 1].first;
      }
      if (cnt_r > 0) {
        ll add = sum_l - sum_r;
        if (cnt_l > cnt_r) add -= last_r * (cnt_l - cnt_r);
        else add += last_l * (cnt_r - cnt_l);
        dp[i] = min(dp[i], dp[j + 1] + add);
        dp[i] = min(dp[i], dp[j] + add);
      } 
      if (seg[j] < seg[i] - 1) break;
    }
  }
  return dp[n + m];
}

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