Submission #249301

#	Time	Username	Problem	Language	Result	Execution time	Memory
249301		kostia244	Wiring (IOI17_wiring)	C++17	100 / 100	116 ms	13048 KiB

wiring

#include "wiring.h"
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int maxn = 1<<19;
const ll inf = 1ll<<60;
inline void minq(ll &a, ll b) {
	a = min(a, b);
}
struct st {
	ll bias = 0;
	multiset<ll> s;
	void insert(ll x) {
		s.insert(x-bias);
	}
	void erase(ll x) {
		s.erase(s.find(x-bias));
	}
	ll min() {
		return (s.empty()?1ll<<60:(bias+*s.begin()));
	}
	void addall(ll x) {
		bias += x;
	}
};
int n, m;
array<int, 2> x[maxn];
ll dp[maxn], ia[maxn];
void calc(int pl, int cl, int cr) {
	st a, b;
	//cout << pl << "here\n";
	for(ll t = 0, mp = dp[cl-1], i = cl; --i >= pl;) {
		t += x[cl][0] - x[i][0];
		mp = min(mp, dp[i-1]);
		ia[i] = mp + t;
		a.insert(ia[i]);
		//cout << ia[i] << '\n';
	}
	for(int i = cl; i < cr; i++) {
		if(i > cl) {
			int mir = cl - (i-cl) - 1;
			if(mir+1 >= pl) {
				ll erval = ia[mir+1] + a.bias;
				a.erase(erval);
				b.insert(erval);
			}
			a.addall(x[i][0] - x[cl][0]);
			b.addall(x[i][0] - x[cl-1][0]);
		}
		dp[i] = min(a.min(), b.min());
	}
	//cout << cl << " -- " << cr << endl;
	//for(int i = 0; i <= n+m; i++) cout << dp[i] << " "; cout << '\n';
}
ll min_total_length(vector<int> r, vector<int> b) {
	n = r.size(), m = b.size();
	for(int i = 0; i < n; i++) x[1+i] = {r[i], 0};
	for(int i = 0; i < m; i++) x[1+n+i] = {b[i], 1};
	sort(x+1, x+n+m+1);
	dp[0] = 0;
	for(int p = 0, i = 1; i <= n+m;) {
		int j = i+1;
		while(j <= n+m && x[j][1] == x[i][1]) j++;
		if(p) calc(p, i, j);
		else for(int t = i; t < j;) dp[t++] = 1ll<<60; 
		p = i;
		i = j;
	}
	return dp[n+m];
}

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