제출 #1197635

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

wiring

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

using namespace std;

#define fr first
#define sc second

using ll = long long;
#define int ll

const int INF = 1e18;

int min_total_length(vector<signed> R, vector<signed> B) {
	int N, M;
	N = R.size();
	M = B.size();

	vector<pair<int, int>> P;
	for (auto &i : R) 
		P.emplace_back(i, 1);
	for (auto &i : B) 
		P.emplace_back(i, -1);
	sort(P.begin(), P.end());
	reverse(R.begin(), R.end());
	reverse(B.begin(), B.end());

	int x = M;
	int r = -INF, b = -INF, D = 0, S = 0;
	vector<pair<int, int>> lst(N + M + 1, {INF, INF});
	lst[M] = {0, 0};

	for (auto &i : P) {
		int E = 0;
		(i.sc == 1 ? R : B).pop_back();
		x += i.sc;
		S += i.fr * i.sc;
		if (i.sc == 1) {
			r = i.fr;
			E = D+i.fr-b;
			if (B.size()) 
				E = min(E, D + B.back() - i.fr);
		}
		if (i.sc == -1) {
			b = i.fr;
			E = D+i.fr-r;
			if (R.size()) 
				E = min(E, D + R.back() - i.fr);
		}
		D = min(E, lst[x].fr + abs(lst[x].sc - S));
		lst[x] = {D, S};
	}
	return D;
}

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