Submission #831573

#	Time	Username	Problem	Language	Result	Execution time	Memory
831573		WLZ	Wiring (IOI17_wiring)	C++17	100 / 100	56 ms	9916 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;
  vector<int> first(n + m + 1), last(n + m + 1);
  first[0] = v[1].first; last[0] = v[1].first;
  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;
      first[seg[i]] = v[i].first;
    }
    last[seg[i]] = v[i].first;
  }
  sz.push_back(len);
  vector<ll> dp(n + m + 1, LINF); dp[0] = 0;
  vector<int> cnt = {0, 0};
  vector<ll> sum = {0, 0};
  int j = 0;
  for (int i = 1; i <= n + m; i++) {
    cnt[v[i].second]++;
    sum[v[i].second] += v[i].first;
    if (seg[i] == 0) continue;
    if (seg[i] != seg[i - 1]) {
      j = i - 1;
      cnt = {1, 1};
      sum[v[i].second] = v[i].first;
      sum[v[j].second] = v[j].first;
    }
    ll cur_cost = sum[v[i].second] - sum[!v[i].second];
    if (cnt[v[i].second] > cnt[!v[i].second]) cur_cost -= (ll) (cnt[v[i].second] - cnt[!v[i].second]) * last[seg[i] - 1];
    else cur_cost += (ll) (cnt[!v[i].second] - cnt[v[i].second]) * first[seg[i]];
    while (seg[j - 1] == seg[i] - 1) {
      dp[i] = min(dp[i], dp[j - 1] + cur_cost);
      dp[i] = min(dp[i], dp[j] + cur_cost);  
      auto tmp_cnt = cnt; auto tmp_sum = sum;
      tmp_cnt[v[j - 1].second]++; tmp_sum[v[j - 1].second] += v[j - 1].first;
      ll new_cost = tmp_sum[v[i].second] - tmp_sum[!v[i].second];
      if (tmp_cnt[v[i].second] > tmp_cnt[!v[i].second]) new_cost -= (ll) (tmp_cnt[v[i].second] - tmp_cnt[!v[i].second]) * last[seg[i] - 1];
      else new_cost += (ll) (tmp_cnt[!v[i].second] - tmp_cnt[v[i].second]) * first[seg[i]];
      if (dp[j - 2] + new_cost <= dp[j - 1] + cur_cost || dp[j - 1] == LINF) {
        cnt = tmp_cnt;
        sum = tmp_sum;
        cur_cost = new_cost;
        j--;
      } else break;
    }
    dp[i] = min(dp[i], dp[j - 1] + cur_cost);
    dp[i] = min(dp[i], dp[j] + cur_cost);
  }
  return dp[n + m];
}

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