| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 497873 | kevin | 전선 연결 (IOI17_wiring) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define all(x) x.begin(), x.end()
#define f first
#define s second
#define ca(v) for(auto i:v) cout<<i<<" ";
#define nl cout<<"\n"
const int MAXN = 5e5 + 5;
ll min_total_length(vector<int> a, vector<int> b){
vector<pair<ll, int>> ar;
for(int i:a) ar.push_back({(ll)i, 0});
for(int i:b) ar.push_back({(ll)i, 1});
sort(ar.begin(), ar.end());
int p = 0;
int pv = -1;
vector<ll> val[2];
// 0 = <, 1 = >, so add
// 0 is pref, 1 is posts
while(p < (int)ar.size()){
vector<ll> v;
ll x = ar[p].f;
v.push_back(x);
while(p < (int)ar.size() - 1 && ar[p].s == ar[p+1].s) v.push_back(ar[++p].f);
// ca(v); nl;
p++;
// cout<<p<<" ";
ll iv = (p == (int)ar.size()?0:ar[p].f-ar[p-1].f);
if(pv == -1){
if(p == (int)ar.size()) return 0;
val[0] = val[1] = vector<ll>(v.size() + 1, 1e18);
ll sm = 0;
for(ll i:v) sm += v.back() - i;
val[0][v.size()] = val[1][v.size()] = sm;
}
else{
// cout<<x<<" "<<pv<<"\n";
vector<ll> nxt[2]; nxt[0] = nxt[1] = vector<ll>(v.size() + 1);
ll lsm = 0;
ll rsm = 0;
for(int i=0; i<(int)v.size(); i++) rsm += v.back() - v[i];
// cout<<lsm<<" "<<rsm<<"\n";
nxt[0][v.size()] = val[0][0] + rsm;
for(int i=1; i<=(int)v.size(); i++){
if(i) {
lsm += v[i-1] - v[0];
rsm -= v.back() - v[i-1];
}
int id = min(i, (int)val[0].size()-1);
// cout<<"Val: "<<val[0][id]<<" "<<(int)(i) * (x-pv)<<" "<<(i<(int)val[1].size()?val[1][i]:1e18)<<" "<<lsm<<" "<<rsm<<"\n";
nxt[0][v.size()-i] = min(val[0][id] + (ll)(i) * (x-pv), (ll)(i<(int)val[1].size()?val[1][i]:1e18)) + lsm + rsm;
}
// nxt[0][0] = val[0][val[0].size()-1] + lsm;
val[0] = nxt[0];
nxt[0].clear(); nxt[1].clear();
}
val[1] = val[0];
pv = ar[p-1].f;
for(int i=0; i<val[0].size(); i++) val[1][i] += i * iv;
// ca(val[0]); nl; ca(val[1]); nl;
for(int i=1; i<(int)val[0].size(); i++){
val[0][i] = min(val[0][i], val[0][i-1]);
val[1][val[0].size()-1-i] = min(val[1][val[0].size()-i], val[1][val[0].size()-1-i]);
}
// ca(val[0]); nl; ca(val[1]); nl; nl;
if(p == ar.size()) return val[0][0];
}
}
int main()
{
// ios_base::sync_with_stdio(0); cin.tie(0);
if (fopen("input.in", "r")) freopen("input.in", "r", stdin);
int N, M; cin>>N>>M;
vector<int> A(N); vector<int> B(M);
for(int i=0; i<N; i++) cin>>A[i];
for(int j=0; j<M; j++) cin>>B[j];
cout<<min_total_length(A, B);
}