제출 #1329486

#제출 시각아이디문제언어결과실행 시간메모리
1329486kawhiet전선 연결 (IOI17_wiring)C++20
0 / 100
1 ms344 KiB
#include <bits/stdc++.h>
#include "wiring.h"
using namespace std;

constexpr int inf = 1e9;

long long min_total_length(vector<int> a, vector<int> b) {
	if (a.size() < b.size()) swap(a, b);
	int n = a.size(), m = b.size();
	long long ans = 0;
	vector<bool> vis(n);
	for (int i = 0; i < m; i++) {
		int mn = inf, pos = -1;
		for (int j = 0; j < n; j++) {
			if (!vis[j] && abs(a[j] - b[i]) < mn) {
				mn = abs(a[j] - b[i]);
				pos = j;
			}
		}
		assert(pos != -1);
		ans += mn;
		vis[pos] = 1;
	}
	for (int i = 0; i < n; i++) {
		if (!vis[i]) {
			int mn = inf;
			for (int j = 0; j < m; j++) {
				mn = min(mn, a[i] - b[j]);
			}
			ans += mn;
		}
	}
	return ans;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...