제출 #1226175

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1226175		The_Samurai	전선 연결 (IOI17_wiring)	C++20	100 / 100	41 ms	8224 KiB

wiring

#include "wiring.h"
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
const ll inf = 1e18;

ll solve(vector<int> a, vector<int> b, bool rev) {
	// sort(a.begin(), a.end());
	// sort(b.begin(), b.end());
	int n = a.size(), m = b.size();
	vector<pair<int, int>> v;
	for (int i = 0; i < n; i++) v.emplace_back(a[i], 0);
	for (int i = 0; i < m; i++) v.emplace_back(b[i], 1);
	sort(v.begin(), v.end());
	if (rev) {
		reverse(v.begin(), v.end());
	}
	deque<int> shit;
	int wh = -1;
	ll ans = 0;
	array<int, 2> last;
	for (auto [x, tp]: v) {
		last[tp] = x;
		if (!shit.empty() and wh != tp) {
			ans += abs(x - shit[0]);
			shit.pop_front();
		} else {
			shit.push_back(x);
			wh = tp;
		}
	}
	for (int x: shit) ans += abs(x - last[!wh]);
	return ans;
}

long long min_total_length(std::vector<int> a, std::vector<int> b) {
	int n = a.size(), m = b.size();
	vector<pair<int, int>> v;
	for (int i = 0; i < n; i++) v.emplace_back(a[i], 0);
	for (int i = 0; i < m; i++) v.emplace_back(b[i], 1);
	sort(v.begin(), v.end());
	vector<int> fr(v.size(), (int) 1e9);
	for (int i = 0; i < v.size(); i++) {
		auto [x, tp] = v[i];
		if (tp) {
			int j = lower_bound(a.begin(), a.end(), x) - a.begin();
			if (j < a.size()) fr[i] = min(fr[i], abs(x - a[j]));
			j--;
			if (j >= 0) fr[i] = min(fr[i], abs(x - a[j]));
		} else {
			int j = lower_bound(b.begin(), b.end(), x) - b.begin();
			if (j < b.size()) fr[i] = min(fr[i], abs(x - b[j]));
			j--;
			if (j >= 0) fr[i] = min(fr[i], abs(x - b[j]));
		}
	}
	vector<int> pref(v.size());
	for (int i = 0; i < v.size(); i++) pref[i] = (i > 0 ? pref[i - 1] : 0) + v[i].second;
	vector<ll> pref2(v.size());
	for (int i = 0; i < v.size(); i++) pref2[i] = (i > 0 ? pref2[i - 1] : 0) + v[i].first;
	vector<ll> dp(v.size(), inf);
	array<int, 2> last{-1, -1};
	for (int i = 0; i < v.size(); i++) {
		dp[i] = (i > 0 ? dp[i - 1] : 0) + fr[i];
		last[v[i].second] = i;
		int j = last[!v[i].second];
		if (j == -1) continue;
		int cnt = i - j;
		if (j + 1 < cnt) continue;
		int sum = pref[j] - (j - cnt >= 0 ? pref[j - cnt] : 0);
		if (v[j].second and sum != cnt) continue;
		if (!v[j].second and sum != 0) continue;
		// cout << i << ' ' << j << endl;
		ll now = (j - cnt >= 0 ? dp[j - cnt] : 0);
		now += (pref2[i] - pref2[j]) - (pref2[j] - (j - cnt >= 0 ? pref2[j - cnt] : 0));
		dp[i] = min(dp[i], now);
	}
	return dp.back();
}

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