| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 69930 | E869120 | 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 "wiring.h"
#include <bits/stdc++.h>
using namespace std;
int R[100009], B[100009], r[100009], b[100009], N, M; vector<int>X[100009];
long long dp[200009];
long long total_sum(long long px, long long py, long long qx, long long qy){
long long ret = 0, cy = py;
for(int i=px;i<=qx;i++){
ret += abs(R[i] - B[cy]);cy++;
}
return ret;
}
void init(){
for(int i=0;i<N;i++){
int minx=(1<<30),minid=-10;
for(int j=0;j<M;j++){if(minx>abs(R[i]-B[j])){minx=abs(R[i]-B[j]);minid=j;}}
X[i].push_back(minid);
}
for(int i=0;i<M;i++){
int minx=(1<<30),minid=-10;
for(int j=0;j<N;j++){if(minx>abs(R[j]-B[i])){minx=abs(R[j]-B[i]);minid=j;}}
X[minid].push_back(i);
}
}
long long getval(long long cx,long long cy){
if(cx<=0 || cy<=0) return (1LL<<60);
long long E1 = cy - cx + N;
long long ex = 0, ey = 0; if(cx > cy) ex = cx - cy; if(cx < cy) ey = cy - cx;
long long vx = total_sum(ex, ey, cx - 1, cy - 1) + dp[E1];
return vx;
}
void writeval(long long cx,long long cy,long long t){
long long E1 = cy - cx + N;
long long ex = 0, ey = 0; if(cx > cy) ex = cx - cy; if(cx < cy) ey = cy - cx;
long long F = total_sum(ex, ey, cx - 1, cy - 1);
dp[E1] = min(dp[E1], t - F);
}
long long min_total_length(vector<int> r, vector<int> b) {
// -------------------------- 第一部：前準備 --------------------------
N = r.size(); for(int i=0;i<N;i++) R[i] = r[i];
M = b.size(); for(int i=0;i<M;i++) B[i] = b[i];
init();
for(int i=0;i<=N+M;i++) dp[i] = (1LL<<60);
for(int i=0;i<N;i++) sort(X[i].begin(),X[i].end());
dp[N]=0;
for(int i=0;i<N;i++){
for(int j=0;j<(int)X[i].size();j++){
long long v0 = getval(i+1,X[i][j]+1);
long long v1 = getval(i+1,X[i][j]); if(v1!=(1LL<<60))v1+=abs(R[i]-B[X[i][j]]);
long long v2 = getval(i, X[i][j]+1); if(v2!=(1LL<<60))v2+=abs(R[i]-B[X[i][j]]);
writeval(i+1,X[i][j]+1,min({v0,v1,v2}));
//cout<<i<<" "<<X[i][j]<<" "<<v0<<" "<<v1<<" "<<v2<<endl;
}
//for(int i=0;i<=N+M;i++) cout<<i<<":"<<dp[i]<<endl;
}
return getval(N, M);
}
int main(){
int n,m;cin>>n>>m;
vector<int>vec1,vec2;
for(int i=0;i<n;i++){int p;cin>>p;vec1.push_back(p);}
for(int i=0;i<m;i++){int p;cin>>p;vec2.push_back(p);}
cout<<min_total_length(vec1,vec2)<<endl;
return 0;
}