제출 #138450

#제출 시각아이디문제언어결과실행 시간메모리
138450Rubanov전선 연결 (IOI17_wiring)C++17
0 / 100
2 ms504 KiB
#include <bits/stdc++.h> #define all(c) c.begin(), c.end() #define pb push_back #define ll long long #define x first #define y second using namespace std; long long min_total_length(std::vector<int> r, std::vector<int> b) { int n = r.size(); int m = b.size(); bool taken[200005] = {}; vector<pair<ll,pair<int,int>>> ve; for (int i = 0; i < n; i++) { int it = lower_bound(all(b),r[i])-b.begin(); if (it == m) { it--; ve.pb({r[i]-b[it],{i,it+n}}); } else { ll dist = b[it]-r[i]; int id = it; it--; if (it >= 0 && r[i]-b[it] < dist) { dist = r[i]-b[it]; id--; } ve.pb({dist,{i,it+n}}); } } for (int i = 0; i < m; i++) { int it = lower_bound(all(r),b[i])-r.begin(); if (it == n) { it--; ve.pb({b[i]-r[it],{i+n,it}}); } else { int dist = r[it]-b[i]; int id = it; it--; if (it >= 0 && b[i]-r[it] < dist) { dist = b[i]-r[it]; id--; } ve.pb({dist,{i+n,it}}); } } sort(all(ve)); reverse(all(ve)); ll ans = 0; for (auto k : ve) { if (taken[k.y.x]) continue; taken[k.y.x] = 1; taken[k.y.y] = 1; ans += k.x; } 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...