제출 #1184960

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1184960		hamzabc	Wiring (IOI17_wiring)	C++20	100 / 100	27 ms	7356 KiB

wiring

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


using namespace std;


long long min_total_length(std::vector<int> r, std::vector<int> b) {
	int Nr = r.size();
	int Nb = b.size();
	std::priority_queue<long long, vector<long long>, greater<>> prB, prR;
	vector<pair<int, bool>> C(Nr + Nb);  // is blue;
	vector<long long> Cclose(Nr + Nb);
	int j = 0;
	for (int i = 0; i < Nr + Nb; i++){
		if (j == Nr){
			C[i].first = b[i - j];
			C[i].second = true;
		}else if (i - j == Nb){
			C[i].first = r[j];
			C[i].second = false;
			j++;
		}else if (b[i - j] < r[j]){
			C[i].first = b[i - j];
			C[i].second = true;
		}else{
			C[i].first = r[j];
			C[i].second = false;
			j++;
		}
	}
	j = 0;
	for (int i = 0; i < Nr + Nb; i++){
		if ((i - j != Nr) && (j == Nb || r[i - j] < b[j])){
			if (j && j < Nb){
				Cclose[i] = min(b[j] - r[i - j], r[i - j] - b[j - 1]);
			}else if (j){
				Cclose[i] = r[i - j] - b[j - 1];
			}else{
				Cclose[i] = b[j] - r[i - j];
			}
		}else{
			if (i - j && i - j < Nr){
				Cclose[i] = min(r[i - j] - b[j], b[j] - r[i - j - 1]);
			}else if (i - j){
				Cclose[i] = b[j] - r[i - j - 1];
			}else{
				Cclose[i] = r[i - j] - b[j];
			}
			j++;
		}
	}
	long long int sum = 0;
	for (int i = 0; i < Nr + Nb; i++){
		if (C[i].second){
			if (prR.size() == 0 || Cclose[i] < C[i].first + prR.top()){
				prB.push(-Cclose[i] - C[i].first);
				sum += Cclose[i];
			}else{
				long long int a = prR.top();
				prR.pop();
				sum += C[i].first + a;
				prB.push(-2 * C[i].first - a);
			}
		}else{
			if (prB.size() == 0 || Cclose[i] < C[i].first + prB.top()){
				prR.push(-Cclose[i] - C[i].first);
				sum += Cclose[i];
			}else{
				long long int a = prB.top();
				prB.pop();
				sum += C[i].first + a;
				prR.push(-2 * C[i].first - a);
			}
		}
	}
	return sum;
}

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