Submission #624197

#	Time	Username	Problem	Language	Result	Execution time	Memory
624197		Clan328	Wiring (IOI17_wiring)	C++17	30 / 100	1084 ms	5192 KiB

wiring

#include "wiring.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef vector<int> vi;

vi mapper, bits;

ll cost(int i, int j) {
	vi r, b;
	for (int k = i; k <= j; k++) {
		if (bits[k] != bits[i]) b.push_back(mapper[k]);
		else r.push_back(mapper[k]);
	}

	int n = r.size(), m = b.size();

	// for (int k = 0; k < n; k++) {
	// 	cout << r[k] << " ";
	// }
	// cout << endl;
	// for (int k = 0; k < m; k++) {
	// 	cout << b[k] << " ";
	// }
	// cout << endl;

	ll res = 0;
	if (n <= m) {
		int idx = n-1;
		for (int i = 0; i < m; i++) {
			if (idx < 0) res += b[i]-r[n-1];
			else {
				res += b[i]-r[idx];
				idx--;
			}
		}
	} else {
		int idx = m-1;
		for (int i = 0; i < n; i++) {
			if (idx < 0) res += b[0]-r[i];
			else {
				res += b[idx]-r[i];
				idx--;
			}
		}
	}

	return res;
}

ll min_total_length(vi r, vi b) {
	int n = r.size(), m = b.size();

	if (r[n-1] < b[0]) { // Subtask 2
		ll res = 0;
		if (n <= m) {
			int idx = n-1;
			for (int i = 0; i < m; i++) {
				if (idx < 0) res += b[i]-r[n-1];
				else {
					res += b[i]-r[idx];
					idx--;
				}
			}
		} else {
			int idx = m-1;
			for (int i = 0; i < n; i++) {
				if (idx < 0) res += b[0]-r[i];
				else {
					res += b[idx]-r[i];
					idx--;
				}
			}
		}

		return res;
	} else if (n <= 200 && m <= 200) {
		vector<vector<ll>> dp(n+1, vector<ll>(m+1));
		for (int i = 1; i <= n; i++) dp[i][0] = LLONG_MAX;
		for (int i = 1; i <= m; i++) dp[0][i] = LLONG_MAX;

		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= m; j++) {
				dp[i][j] = abs(r[i-1]-b[j-1]) + min(dp[i-1][j-1], min(dp[i-1][j], dp[i][j-1]));
				// cout << i << " " << j << " " << dp[i][j] << endl;
			}
		}

		return dp[n][m];
	}
	// n = 19;

	// 0 Red 1 Blue
	bits = vi(n+m);
	mapper = vi(n+m);
	int idxR = 0, idxB = 0;
	while (idxR < n || idxB < m) {
		if (idxR < n && idxB < m) {
			bits[idxR+idxB] = (r[idxR] > b[idxB]);
			mapper[idxR+idxB] = min(r[idxR], b[idxB]);
			if (r[idxR] < b[idxB]) idxR++;
			else idxB++;
		} else if (idxR < n) {
			bits[idxR+idxB] = 0;
			mapper[idxR+idxB] = r[idxR];
			idxR++;
		} else {
			bits[idxR+idxB] = 1;
			mapper[idxR+idxB] = b[idxB];
			idxB++;
		}
	}

	vector<ll> dp(n+m, LLONG_MAX);
	int start = 0, end = 0, i = 0;
	while (bits[i] == bits[0]) {
		end++;
		i++;
	}

	for ( ; i < n+m; i++) {
		for (int j = start; j < end; j++) {
			if ((j > 0 && dp[j-1] != LLONG_MAX) || (j == 0)) {
				dp[i] = min(dp[i], (j > 0 ? dp[j-1] : 0) +cost(j, i));
			}
			if (dp[j] != LLONG_MAX) dp[i] = min(dp[j] +cost(j, i), dp[i]);
		}

		// cout << i << " " << start << " " << end << endl;

		if (i < n+m-1 && bits[i] != bits[i+1]) {
			start = end;
			end = i+1;
		}
		// cout << dp[i] << endl;
	}

	// cout << dp[36] << endl;

	return dp[n+m-1];
}

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