| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 313134 | kylych03 | 전선 연결 (IOI17_wiring) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "wiring.h"
#include <bits/stdc++.h>
#include "grader.cpp"
#define ll long long
using namespace std;
long long dp[200002];
long long inf = 1e15;
long long MAXN =200005;
long long balance[200005];
long long pref[200005];
vector <int> r,b;
int getMin(pair<ll, bool> curr) {
if(curr.second) {
auto it = lower_bound(r.begin(), r.end(), curr.first);
long long mn = inf;
if(it != r.end())
mn = min(mn, *it - curr.first);
if(it != r.begin())
{it --; mn = min(mn, curr.first - *it);}
return mn;
} else {
auto it = lower_bound(b.begin(), b.end(), curr.first);
long long mn = inf;
if(it != b.end())
mn = min(mn, *it - curr.first);
if(it != b.begin()) {
it --; mn = min(mn, curr.first - *it);
}
return mn;
}
}
long long min_total_length(std::vector<int> r1, std::vector<int> b1) {
vector < pair <ll, bool> > pr;
int n = r1.size();
int m = b1.size();
pr.resize(n+m);
r.resize(n);
r=r1;
b.resize(m);
b=b1;
for(int i = 0 ; i < n; i++){
pr[i].first = r1[i];
pr[i].second = 0;
}
for(int i = 0 ; i < m; i++){
pr[i+n].first = b1[i];
pr[i+n].second = 1;
}
pr.push_back(make_pair(-inf, 0));
sort(pr.begin(), pr.end());
for(int i = 0 ; i < MAXN; i++)
balance[i]=-1;
long long curr = MAXN / 2;
balance[curr] = 0;
dp[0]=0;
for(int i = 1 ; i <= n + m ; i++){
if(pr[i].second) {
pref[i] = pref[i -1] - pr[i].first;
curr --;
} else {
pref[i] = pref[i -1] + pr[i].first;
curr ++;
}
dp[i] = dp[i-1] + getMin(pr[i]);
if(balance[curr]!=-1){
dp[i] = min(dp[i], dp[balance[curr]] + abs(pref[i] - pref[balance[curr]]));
}
balance[curr] = i;
}
return dp[n+m];
}