Submission #206573

#	Time	Username	Problem	Language	Result	Execution time	Memory
206573		impetus_	Wiring (IOI17_wiring)	C++14	100 / 100	75 ms	21352 KiB

wiring

#include<bits/stdc++.h>

#define pb push_back
#define mp make_pair
#define sz(x) (int)x.size()
#define f first
#define s second
#define all(x) x.begin(), x.end()
#define forn(i, a, b) for(int i = a; i <= b; i++)
#define forev(i, a, b) for(int i = a; i >= b; i--)

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef vector<pii> vpii;

const int maxn = (int)1e6 + 100;
const int mod = (int)1e9 + 7;
const int inf = (int)2e9;
const double pi = acos(-1.0);

int n, m, a, b, go[maxn], was[2], cnt[maxn], used[maxn + maxn], K = 500000;
ll dp[maxn], s[maxn];
vpii v;
ll min_total_length(vi v1, vi v2) {
  n = sz(v1), m = sz(v2);
  for(auto a : v1) v.pb(mp(a, 0));
  for(auto b : v2) v.pb(mp(b, 1));
  sort(all(v));
  forn(i, 0, maxn - 1) go[i] = inf;
  was[0] = was[1] = -1; 
  int i = 0;
  for(auto x : v){
    i++;
    if(was[!x.s] != -1) go[i] = x.f - was[!x.s];
    was[x.s] = x.f;
    if(x.s) cnt[i] = 1, s[i] = x.f;
    else cnt[i] = -1, s[i] = -x.f;
    cnt[i] += cnt[i - 1];
    s[i] += s[i - 1];
  }
  was[0] = was[1] = -1; i = n + m + 1;
  reverse(all(v));
  for(auto x : v){
    i--;
    if(was[!x.s] != -1) go[i] = min(go[i], was[!x.s] - x.f);
    was[x.s] = x.f;
  }
  memset(used, -1, sizeof(used));
  used[K] = 0;
  forn(i, 1, n + m){
    dp[i] = dp[i - 1] + go[i];
    if(used[cnt[i] + K] != -1){
      int j = used[cnt[i] + K] + 1;
      dp[i] = min(dp[i], dp[j - 1] + abs(s[i] - s[j - 1]));
    }
    used[cnt[i] + K] = i;
  }
  return dp[n + m];
}

/*
int main() {
	int n, m;
	assert(2 == scanf("%d %d", &n, &m));

	vector<int> r(n), b(m);
	for(int i = 0; i < n; i++)
		assert(1 == scanf("%d", &r[i]));
	for(int i = 0; i < m; i++)
		assert(1 == scanf("%d", &b[i]));

	long long res = min_total_length(r, b);
	printf("%lld\n", res);

	return 0;
}
*/
// to check runtime errors
// special case

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