제출 #789926

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
789926		Sohsoh84	전선 연결 (IOI17_wiring)	C++17	17 / 100	1084 ms	6712 KiB

wiring

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

using namespace std;

#define all(x)		(x).begin(), (x).end()
#define X		first
#define Y		second
#define sep		' '
#define debug(x)	cerr << #x << ": " << x << endl;

typedef long long ll;
typedef pair<ll, ll> pll;

const ll MAXN = 1e6 + 10;
const ll INF = 1e15 + 10;

ll dp[MAXN];

ll min_total_length(vector<int> r, vector<int> b) {
	vector<pll> vec;
	vec.push_back({-1, -1});
	for (int i = 0; i < int(r.size()); i++) vec.push_back({r[i], 0});
	for (int i = 0; i < int(b.size()); i++) vec.push_back({b[i], 1});

	sort(all(vec));
	dp[0] = 0;
	int lst[2] = {0, 0};

	int n = int(vec.size()) - 1;
	for (int i = 1; i <= n; i++) {
		auto [x, t] = vec[i];
		lst[t] = i;
		
		int ind = lst[t ^ 1];
		int y = vec[ind].X;
		if (ind == 0) {
			dp[i] = INF;
			continue;
		}
	
		dp[i] = dp[i - 1] + x - y;
		ll s1 = 0, s2 = 0, f = 0;
		for (int j = i; j > ind; j--) {
			s1 += vec[j].X;
		}

		for (int j = ind; j > 0 && vec[j].Y != t; j--) {
			if (ind - j <= i - (ind + 1)) s2 += vec[j].X;
			else f += vec[ind + 1].X - vec[j].X;
			if (ind - j >= i - (ind + 1)) dp[i] = min(dp[i], dp[j - 1] + s1 - s2 + f);
		}
	}

	return dp[n];
}

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