| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1339611 | settop | 전선 연결 (IOI17_wiring) | C++20 | 0 ms | 0 KiB |
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fall(i,a,b) for(int i=a;i<=b;i++)
#define rfall(i,a,b) for(int i=a;i>=b;i--)
#define all(x) x.begin(),x.end()
#define F first
#define S second
#define sz(x) (int)x.size()
#define pb push_back
const int MAXN=2e5+10;
const ll inf=1e16;
typedef pair<int,int> pii;
typedef tuple<int,int,int> trio;
ll dp[MAXN][100];
int main(){
int n,m; cin>>n>>m;
vector<int> r(n),b(m);
for(auto &u:r) cin>>u;
for(auto &u:b) cin>>u;
vector<pii> v(n+m);
fall(i,0,n-1) v[i]={r[i],0};
fall(i,0,m-1) v[i+n]={b[i],1};
sort(all(v));
fall(mask,0,63) dp[n+m-1][mask]=inf;
dp[n+m-1][1]=0;
rfall(i,n+m-2,0){
rfall(mask,63,0){
dp[i][mask]=inf;
if((mask&1)) dp[i][mask]=dp[i+1][mask>>1];
fall(j,i+1,min(i+6,m+n-1)){
if(v[i].S==v[j].S) continue;
if(j==i+6) dp[i][mask]=min(dp[i][mask],dp[i+1][(mask>>1)+32]+v[j].F-v[i].F);
else dp[i][mask]=min(dp[i][mask],dp[i][(mask|1)|(1<<(j-i))]+v[j].F-v[i].F);
}
}
}
cout<<dp[0][0]<<"\n";
}