Submission #1213457

#	Time	Username	Problem	Language	Result	Execution time	Memory
1213457		sano	Wiring (IOI17_wiring)	C++20	100 / 100	47 ms	14828 KiB

wiring

#include "wiring.h"
#include<iostream>
#include<vector>
#include<queue>
#include<deque>
#include<string>
#include<fstream>
#include<algorithm>
#include <iomanip>
#include<map>
#include <set>
#include <unordered_map>
#include <stack>
#include <unordered_set>
#include <cmath>
#include <random>
#define ll long long
#define For(i, n) for(ll i = 0; i < (ll)n; i++)
#define ffor(i, a, n) for(ll i = (ll)a; i < (ll)n; i++)
#define rfor(i, n) for(ll i = (ll)n; i >= (ll)0; i--)
#define rffor(i, a, n) for(ll i = (ll)n; i >= (ll)a; i--)
#define vec vector
#define ff first
#define ss second
#define pb push_back
#define shit short int
#define pii pair<ll, ll>
#define NEK 10000000000000000
#define mod 1000000007
#define mod2 1000000009
#define rsz resize 
#define prv1 43
#define prv2 47
using namespace std;

ll min_total_length(vec<int> r2, vec<int> b2) {
	vec<ll> r, b;
	vec<pii> p;
	For(i, r2.size()) r.push_back(r2[i]);
	For(i, b2.size()) b.push_back(b2[i]);
	ll pr = r.size();
	ll p_b = b.size();
	ll n = pr + p_b;
	For(i, pr) {
		p.push_back({ r[i], 0 });
	}
	For(i, p_b) {
		p.push_back({ b[i], 1 });
	}
	sort(p.begin(), p.end());
	vec<ll> dp(n + 1, NEK);
	dp[0] = 0;
	vec<ll> bl(n, NEK);
	ll pos0 = -1, pos1 = -1;
	For(i, n) {
		if (p[i].ss == 0) {
			pos0 = p[i].ff;
			if (pos1 == -1) continue;
			bl[i] = min(bl[i], p[i].ff - pos1);
		}
		if (p[i].ss == 1) {
			pos1 = p[i].ff;
			if (pos0 == -1) continue;
			bl[i] = min(bl[i], p[i].ff - pos0);
		}
	}
	pos0 = -1, pos1 = -1;
	rfor(i, n-1) {
		if (p[i].ss == 0) {
			pos0 = p[i].ff;
			if (pos1 == -1) continue;
			bl[i] = min(bl[i], pos1 - p[i].ff);
		}
		if (p[i].ss == 1) {
			pos1 = p[i].ff;
			if (pos0 == -1) continue;
			bl[i] = min(bl[i], pos0 - p[i].ff);
		}
	}

	ll prvy = 0;
	ll posl = 0;
	ll pointer = -1;
	vec<ll> p_vzd(n, -1);
	ll trz_vzd = 0;
	priority_queue<pii> q;
	ll min_pred = NEK;
	ffor(i, 1, n + 1) {
		//jednoducho ho napoj na najblizsieho
		dp[i] = min(dp[i], dp[i - 1] + bl[i - 1]);
		if (p[i - 1].ss != p[prvy].ss) {
			while (!q.empty()) q.pop();
			ll vzd = 0;
			for (ll j = i - 2; j >= prvy; j--) {
				vzd += p[i - 2].ff - p[j].ff;
				p_vzd[j] = vzd;
				q.push({ (dp[j] + vzd + (i - 1 - j) * (p[i - 1].ff - p[i - 2].ff)) * (-1), j});
			}
			posl = prvy;
			pointer = i - 2;
			prvy = i - 1;
			trz_vzd = 0;
			min_pred = NEK;
		}
		trz_vzd += p[i-1].ff - p[prvy].ff;
		//vzd1 jedna co si budem predpocitavat
		//trz_vzd + vzd2 + dp[i-1] + MAX(POCA, POCB) * (dist)
		ll pocb = (i - prvy);
		while (pointer >= posl && (prvy - pointer) <= (i - prvy)) {
			min_pred = min(min_pred, p_vzd[pointer] + dp[pointer]);
			pointer--;
		}
		//musime vyhodit vsetkych mojov ktory uz zrazu niesu v ponuke
		while (!q.empty()) {
			if (q.top().ss > pointer) q.pop();
			else break;
		}
		ll min_druhe = NEK;
		if (!q.empty()) {
			min_druhe = q.top().ff * (-1) + trz_vzd;
		}
		ll odp = NEK;
		if (prvy != 0) {
			odp = min_pred + trz_vzd + pocb * (p[prvy].ff - p[prvy - 1].ff);
		}
		dp[i] = min(dp[i], min(min_druhe, odp));
	}
	return dp[n];
}
/*
signed main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	int n, m; cin >> n >> m;
	vec<int> a(n), b(m);
	For(i, n) cin >> a[i];
	For(i, m) cin >> b[i];
	cout << min_total_length(a, b) << '\n';
	return 0;
}*/

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