| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 147916 | neki | Wiring (IOI17_wiring) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#include "wiring.h"
#define maxn 100100
#define loop(i, a, b) for(int i=a;i<b;i++)
typedef long long ll
using namespace std;
bool cmp(ll a, ll b) { return (abs(a)<abs(b))? 1:0;}
ll min(ll a, ll b) { return (a<b)? a:b;}
long long min_total_length (vector <int> red, vector <int> blue) {
pair<ll, ll> com[maxn*2];n=red.size()+blue.size();
loop(i, 0, red.size()) com[i]({red[i], 1});
loop(i, 0, blue.size()) com[i+red.size()]({blue[i], -1});
sort(com, com+n, cmp);sort(red.begin(), red.end());sort(blue.begin(), blue.end());
ll dp[maxn*2], nek[maxn*2], ind[maxn*2], bal=maxn;loop(i, 0, 2*maxn) nek[i]=LLONG_MAX, dif=0;
loop(i, 0, n){
ll ma=LLONG_MAX;
bal+=com[i].second;dif+=com[i].first * com[i].second;
if(com[i].second==1){
auto cl=lower_bound(blue.begin(), blue.end(), com[i].first);
if(cl!=blue.end()) ma=min(ma, (*cl)-com[i].first);
if(cl!=blue.begin()) ma=min(ma, com[i].first-(*prev(cl)));
}
else{
auto cl=lower_bound(red.begin(), red.end(), com[i].first);
if(cl!=red.end()) ma=min(ma, (*cl)-com[i].first);
if(cl!=red.begin()) ma=min(ma, com[i].first-(*prev(cl)));
}
dp[i]=min(dp[i-1]+ma, abs(dif-nek[bal])+dp[ind[bal]]);
nek[bal]=dif;ind[bal]=i;
}
return dp[n-1];
}