제출 #73047

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
73047		nvmdava	전선 연결 (IOI17_wiring)	C++17	0 / 100	3 ms	436 KiB

wiring

#include "wiring.h"
#include <bits/stdc++.h>
using namespace std;

struct Node{
	int id, c;
	Node(int _id, int _c){
		id = _id;
		c = _c;
	}
	bool operator<(const Node& rhs) const{
		return id < rhs.id;
	}
};

vector<Node> v;
long long ans[200005];
int lr[200005], lb[200005];
long long min_total_length(std::vector<int> r, std::vector<int> b) {
	
	lr[0] = -1;
	lb[0] = -1;
	int all = b.size() + r.size();

	for(auto x : r){
		v.push_back(Node(x, 1));
	}
	for(auto x : b){
		v.push_back(Node(x, 0));
	}
	sort(v.begin(), v.end());
	int i;
	for(i = 0; i < all; i++){
		lr[i + 1] = lr[i];
		lb[i + 1] = lb[i];
		if(v[i].c) lr[i + 1] = i;
		else lb[i + 1] = i;
	}
	
	for(i = 1; i <= all; i++){
		
		ans[i] = ans[i - 1] - v[i - 1].id;
		
		if(lr[i] < 0 || lb[i] < 0) continue;
		break;
	}
	ans[i] += v[i - 1].id * i;
	for(i = i + 1; i <= all; i++){
		ans[i] = ans[i - 1] + v[i - 1].id - (v[i - 1].c == 1 ? v[lb[i]].id : v[lr[i]].id);
		if(v[i - 1].c + v[i - 2].c == 1){
			if(ans[i - 2] <= 0) continue;
			ans[i] = min(ans[i], ans[i - 2] + v[i - 1].id - v[i - 2].id);
		}
	}
	return ans[all];
}

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