Submission #1025713

#	Time	Username	Problem	Language	Result	Execution time	Memory
1025713		AmirAli_H1	Wiring (IOI17_wiring)	C++17	100 / 100	44 ms	11976 KiB

wiring

// In the name of Allah
 
#include <bits/stdc++.h>
#include "wiring.h"
using namespace std;
 
typedef		long long int			ll;
typedef		long double				ld;
typedef		pair<int, int>			pii;
typedef		pair<ll, ll>			pll;
typedef		complex<ld>				cld;
 
#define		all(x)					(x).begin(),(x).end()
#define		len(x)					((ll) (x).size())
#define		F						first
#define		S						second
#define		X						real()
#define		Y						imag()
#define		pb						push_back
#define		sep						' '
#define		endl					'\n'
#define		Mp						make_pair
#define		kill(x)					cout << x << '\n', exit(0)
#define		set_dec(x)				cout << fixed << setprecision(x);
#define		file_io(x,y)			freopen(x, "r", stdin); freopen(y, "w", stdout);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
int n, m;
const int maxn = 2e5 + 4;
const ll oo = 1e18 + 4;
vector<pair<ll, pll>> A;
int val[maxn]; ll dp[maxn], sm[maxn];

ll min_total_length(vector<int> r, vector<int> b) {
	n = len(r); m = len(b);
	
	for (int i = 0; i < n; i++) {
		ll x = oo;
		int j = lower_bound(all(b), r[i]) - b.begin();
		if (j < len(b)) x = min(x, (ll) abs(r[i] - b[j]));
		if (j - 1 >= 0) x = min(x, (ll) abs(r[i] - b[j - 1]));
		A.pb(Mp(r[i], Mp(x, 0)));
	}
	for (int i = 0; i < m; i++) {
		ll x = oo;
		int j = lower_bound(all(r), b[i]) - r.begin();
		if (j < len(r)) x = min(x, (ll) abs(b[i] - r[j]));
		if (j - 1 >= 0) x = min(x, (ll) abs(b[i] - r[j - 1]));
		A.pb(Mp(b[i], Mp(x, 1)));
	}
	sort(all(A));
	
	sm[0] = 0;
	for (int i = 1; i <= len(A); i++) {
		sm[i] = sm[i - 1] + A[i - 1].F;
		if (i - 1 >= 1 && A[i - 1].S.S == A[i - 2].S.S) val[i] = val[i - 1] + 1;
		else val[i] = 1;
	}
	
	for (int i = 1; i <= len(A); i++) {
		dp[i] = dp[i - 1] + A[i - 1].S.F;
		if (val[i] < i && val[i - val[i]] >= val[i]) {
			int j = val[i];
			ll R = (sm[i] - sm[i - j]) - (sm[i - j] - sm[i - 2 * j]);
			dp[i] = min(dp[i], dp[i - 2 * j] + R);
		}
	}
	return dp[len(A)];
}

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