| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 428999 | REALITYNB | 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 int2 __int32
#define int long long
#define all(a) a.begin(),a.end()
#define pb push_back
using namespace std;
const int inf = 1e18 ;
int min_total_length(vector<int2> r,vector<int2> bb){
vector<int> a ;
for(int2&x:r) ++x ;
for(int2&x: bb) ++x;
for(int x:r) a.pb(x) ;
for(int x:bb) a.pb(-x) ;
sort(all(a),[&](int x,int y){return abs(x) <abs(y) ; });
int n = a.size() ;
vector<vector<int>> b ;
for(int i=0;i<n;i++){
int sz = 0 ;
vector<int> hey ;
for(int j=i;j<n;j++){
if(a[i]*a[j]<0) break ;
hey.pb(j);
i=j ;
}
b.pb(hey);
}
for(int&x:a)if(x<0) x*=-1 ;
for(int&x:a) --x;
/*cout << b.size() << endl ;
for(auto x :b){
for(int y:x) cout << y << " ";
cout << endl ;
}*/
vector<int> dp(n,inf) ;
int sumi = 0 ;
for(int x:b[0]) sumi+=a[x] ;
int loli = a[b[1][0]]*(b[0].size()) ;
for(int i=0;i<b[1].size();i++){
loli+=a[b[1][i]];
if(i+1>b[0].size()){
sumi+=a[b[0].back()];
}
else loli-=a[b[1][0]];
// cout << loli << " " << sumi << " "<< a[b[1][0]] << endl ;
dp[b[1][i]]=loli-sumi ;
}
dp[b[0].back()]=dp[b[1][0]];
for(int i=2;i<b.size();i++){
int prev = dp[b[i-1].back()] ;
int lol = b[i-1].back();
int sum = 0 ;
for(int j=0;j<b[i].size();j++){
prev+=a[b[i][j]];
prev-=a[b[i-1].back()] ;
if(lol-j>=b[i-1][0]){
sum+=a[b[i][j]];
sum-=a[lol-j];
prev=min(prev,dp[lol-j-1]+sum) ;
}
dp[b[i][j]]=min(dp[b[i][j]],prev) ;
}
int mn = min(b[i].size(),b[i-1].size()) ;
prev=inf;
sum = 0;
for(int j=0;j<mn;j++) sum+=a[b[i][j]];
for(int j=b[i-1].size()-1;j>lol-mn;j--) sum-=a[b[i-1][j]];
for(int j=mn-1;j>-1;j--){
prev=min(prev,sum+dp[lol-j-1]) ;
dp[b[i][j]]=min(dp[b[i][j]],prev) ;
prev-=a[b[i][j]];
prev+=a[b[i][0]];
sum-=a[b[i][j]] ;
sum+=a[lol-j];
}
}
// for(int x: dp) cout << x << " " ;
return dp.back() ;
}