Submission #827165

#	Time	Username	Problem	Language	Result	Execution time	Memory
827165		tranxuanbach	Wiring (IOI17_wiring)	C++17	0 / 100	1083 ms	11148 KiB

wiring

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

#define fi first
#define se second
#define For(i, l, r) for (auto i = (l); i < (r); i++)
#define ForE(i, l, r) for (auto i = (l); i <= (r); i++)
#define FordE(i, l, r) for (auto i = (l); i >= (r); i--)
#define bend(a) (a).begin(), (a).end()
#define isz(a) ((ll)(a).size())

using ll = long long;

const ll infll = (ll)1e18 + 7;

const int N = 2e5 + 5;

struct line_container{
	struct line_type{
		ll a, b;
		mutable ll p;
		bool operator< (const line_type& oth) const{
			return a < oth.a;
		}
		bool operator< (ll x) const{
			return p < x;
		}
	};

	multiset <line_type, less<>> mts;
	const ll inf = infll;

	ll div(ll x, ll y){
		return x / y - ((x ^ y) < 0 and x % y);
	}

	template <class T>
	bool isect(T x, T y){
		if (y == mts.end()){
			x->p = infll;
			return false;
		}
		if (x->a == y->a){
			x->p = x->b > y->b ? infll : -infll;
		}
		else{
			x->p = div(y->b - x->b, x->a - y->a);
		}
		return x->p >= y->p;
	}

	void insert(const line_type& l){
		auto z = mts.insert(l), y = z++, x = y;
		while (isect(y, z)){
			z = mts.erase(z);
		}
		if (x != mts.begin() and isect(--x, y)){
			isect(x, mts.erase(y));
		}
		while ((y = x) != mts.begin() and (--x)->p >= y->p){
			isect(x, mts.erase(y));
		}
	}

	ll query(ll x){
		auto l = *mts.lower_bound(x);
		return l.a * x + l.b;
	}
};

int n, m;
bool col[N];

pair <int, int> pre[N][2];
ll pref[N][2];
ll dp[N];

ll min_total_length(vector <int> r, vector <int> b){
	n = isz(r);
	m = isz(b);
	for (auto pos: r){
		col[pos] = true;
	}
	for (auto pos: b){
		col[pos] = false;
	}
	pre[0][0] = pair{0, 0};
	pre[0][1] = pair{0, 0};
	ForE(i, 1, n + m){
		pre[i][0] = pre[i - 1][0];
		pre[i][1] = pre[i - 1][1];
		swap(pre[i][col[i]].fi, pre[i][col[i]].se);
		pre[i][col[i]].fi = i;
		// cout << i << ' ' << pre[i][0].fi << ' ' << pre[i][0].se << ' ' << pre[i][1].fi << ' ' << pre[i][1].se << endl;
	}
	pref[0][0] = 0;
	pref[0][1] = 0;
	ForE(i, 1, n + m){
		pref[i][0] = pref[i - 1][0] + (col[i] == 0 ? i : 0);
		pref[i][1] = pref[i - 1][1] + (col[i] == 1 ? i : 0);
	}

	fill(dp, dp + n + m + 1, infll);
	dp[0] = 0;
	ForE(i, 1, n + m){
		if (pre[i][0].fi == 0 or pre[i][1].fi == 0){
			continue;
		}
		int j = pre[i][col[i] ^ 1].fi;
		dp[i] = min(dp[i], i - j + dp[i - 1]);
		int k = pre[j][col[i]].fi;
		int leni = i - j, lenj = j - k;
		if (leni <= lenj){
			ll sum = (pref[i][col[i]] - pref[j][col[i]]) - (pref[j][col[i] ^ 1] - pref[j - leni][col[i] ^ 1]);
			for (int l = j - leni; l >= k; l--){
				dp[i] = min(dp[i], sum + dp[l]);
				sum += (j + 1) - l;
			}
		}
		// cout << i << ' ' << dp[i] << endl;
	}
	return dp[n + m];
}

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