Submission #1042168

#	Time	Username	Problem	Language	Result	Execution time	Memory
1042168		NeroZein	Wiring (IOI17_wiring)	C++17	100 / 100	57 ms	11976 KiB

wiring

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

using namespace std;

const int N = 2e5 + 5;  

long long dp[N];
long long pref[N];
int nxt[N], pre[N], lst[N * 2];

long long min_total_length(vector<int> r, vector<int> b) {
  vector<pair<int, int>> a;
  for (int i : r) {
    a.push_back({i, 0});
  }
  for (int i : b) {
    a.push_back({i, 1});
  }
  int n = (int) a.size();
  a.push_back({0, -1});
  sort(a.begin(), a.end());
  pre[0] = pre[1] = -1; 
  for (int i = n; i >= 1; --i) {
    nxt[i] = -1; 
    pre[a[i].second] = i;
    if (pre[1 - a[i].second] != -1) {
      nxt[i] = pre[1 - a[i].second];
    }
  }
  fill(lst, lst + N * 2, -1);
  lst[n] = 0; 
  pre[0] = pre[1] = -1; 
  for (int i = 1, s = 0; i <= n; ++i) {
    dp[i] = LLONG_MAX;
    if (nxt[i] != -1) {
      dp[i] = dp[i - 1] + a[nxt[i]].first - a[i].first; 
    }
    if (pre[1 - a[i].second] != -1) {
      dp[i] = min(dp[i], dp[i - 1] + a[i].first - a[pre[1 - a[i].second]].first);
    }
    pre[a[i].second] = i; 
    int sign = 2 * a[i].second - 1; 
    s += sign; 
    pref[i] = pref[i - 1] + a[i].first * sign; 
    if (lst[s + n] != -1) {
      dp[i] = min(dp[i], dp[lst[s + n]] + llabs(pref[i] - pref[lst[s + n]]));
    }
    lst[s + n] = i; 
    //cout << "i: " << i << ' ' << dp[i] << endl;
  }
  return dp[n];
}

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