| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 147916 | neki | Wiring (IOI17_wiring) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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];
}