Submission #1144562

#	Time	Username	Problem	Language	Result	Execution time	Memory
1144562		gyg	전선 연결 (IOI17_wiring)	C++20	7 / 100	15 ms	2316 KiB

wiring

#include "wiring.h"
#include <bits/stdc++.h>
using namespace std;
#define sig signed
#define int long long
#define arr array
#define vec vector
#define pii pair<int, int>
#define fir first 
#define sec second 
const int N = 5e3 + 5, INF = 1e18;

int n;
arr<pii, N> a;

vec<vec<int>> rng;
void rng_cmp() {
	for (int i = 1; i <= n; i++) {
		if (rng.empty() || a[i].sec != rng.back()[2]) rng.push_back({i, i, a[i].sec});
		else rng.back()[1] = i;
	}
}

int scr(int l1, int r1, int l2, int r2) {
	int ans = 0;
	for (int i = l1; i <= r1; i++) ans -= a[i].fir; // Fixed
	for (int i = l2; i <= r2; i++) ans += a[i].fir; // Varies with i
	
	int sz1 = r1 - l1 + 1, sz2 = r2 - l2 + 1;
	if (sz1 > sz2) ans += (sz1 - sz2) * a[l2].fir;
	else ans -= (sz2 - sz1) * a[r1].fir;
	return ans;
}

arr<int, N> vl;
set<pii> ls, mr;
int ls_add, mr_add;
void mv(int i) {
	assert(1 <= i && i <= n);
	mr.erase({vl[i], i});
	ls.insert({vl[i] + mr_add - ls_add, i});
}

arr<int, N> dp;
void dp_cmp() {
	int prf = 0;
	for (int i = 1; i <= n; i++) {
		dp[i] = INF;
		vec<int> tr = {i, INF, INF};
		int cr = upper_bound(rng.begin(), rng.end(), tr) - 1 - rng.begin(), prv = cr - 1;;
		if (cr == 0) continue;

		int l1 = rng[prv][0], r1 = rng[prv][1], l2 = rng[cr][0];
		if (i == l2) {
			ls = mr = {};
			ls_add = mr_add = 0;
			prf = 0;
			
			int sff = 0;
			for (int j = r1; j >= l1; j--) {
				sff -= a[j].fir;
				vl[j] = min(dp[j - 1], dp[j]) + sff + (r1 - j) * a[l2].fir;
				mr.insert({vl[j], j});
				// cout << "VL " << j << ": " << vl[j] << endl;
				// cout << min(dp[j - 1], dp[j]) << " " << sff << " " << (r1 - j) * a[l2].fir << endl;
			}
		} else {
			mr_add -= a[l2].fir;
			ls_add -= a[r1].fir;
		}

		// cout << "SET " << i << endl;
		// cout << "MR: " << mr_add << endl;
		// for (pii x : mr) cout << x.fir << " " << x.sec << endl;
		// cout << "LS: " << ls_add << endl; 
		// for (pii x : ls) cout << x.fir << " " << x.sec << endl;

		prf += a[i].fir;

		if (mr.size()) dp[i] = min(dp[i], prf + mr.begin()->fir + mr_add);
		if (ls.size()) dp[i] = min(dp[i], prf + ls.begin()->fir + ls_add);

		if (l2 - (i - r1) >= l1) mv(l2 - (i - r1));

		// cout << i << ": " << dp[i] << endl;
	}
}

struct Chck {
	int n;
	arr<pii, N> a;

	vec<vec<int>> rng;
	void rng_cmp() {
		for (int i = 1; i <= n; i++) {
			if (rng.empty() || a[i].sec != rng.back()[2]) rng.push_back({i, i, a[i].sec});
			else rng.back()[1] = i;
		}
	}

	int scr(int l1, int r1, int l2, int r2) {
		int ans = 0;
		for (int i = l1; i <= r1; i++) ans -= a[i].fir;
		for (int i = l2; i <= r2; i++) ans += a[i].fir;
		
		int sz1 = r1 - l1 + 1, sz2 = r2 - l2 + 1;
		if (sz1 > sz2) ans += (sz1 - sz2) * a[l2].fir;
		else ans -= (sz2 - sz1) * a[r1].fir;
		return ans;
	}

	arr<int, N> dp;
	void dp_cmp() {
		for (int i = 1; i <= n; i++) {
			dp[i] = INF;
			vec<int> tr = {i, INF, INF};
			int cr = upper_bound(rng.begin(), rng.end(), tr) - 1 - rng.begin();
			if (cr == 0) continue;
			int prv = cr - 1;

			for (int j = rng[prv][0]; j <= rng[prv][1]; j++) {
				int trns = min(dp[j - 1], dp[j]) + scr(j, rng[prv][1], rng[cr][0], i);
				dp[i] = min(dp[i], trns);
				// cout << i << " " << j << ": " << trns << endl;
			}
			// cout << i << ": " << dp[i] << endl;
		}
	}

	int min_total_length(vec<sig> _a0, vec<sig> _a1) {
	n = _a0.size() + _a1.size();
	for (int i = 1; i <= _a0.size(); i++) a[i] = {_a0[i - 1], 0};
	for (int i = _a0.size() + 1; i <= n; i++) a[i] = {_a1[i - _a0.size() - 1], 1};
	sort(a.begin() + 1, a.begin() + n + 1);
	rng_cmp();
	dp_cmp();
	return dp[n];
}
} chck;

int min_total_length(vec<sig> _a0, vec<sig> _a1) {
	n = _a0.size() + _a1.size();
	for (int i = 1; i <= _a0.size(); i++) a[i] = {_a0[i - 1], 0};
	for (int i = _a0.size() + 1; i <= n; i++) a[i] = {_a1[i - _a0.size() - 1], 1};
	sort(a.begin() + 1, a.begin() + n + 1);

	// chck.min_total_length(_a0, _a1);

	rng_cmp();
	dp_cmp();

	// int ans = dp[n];
	// int chck_ans = chck.min_total_length(_a0, _a1); 
	// if (ans != chck_ans) {
	// 	cout << "AHH" << endl;
	// }

	return dp[n];
}

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