| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 584400 | perchuts | 전선 연결 (IOI17_wiring) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define all(x) x.begin(), x.end()
#define sz(x) (int) x.size()
#define endl '\n'
#define pb push_back
#define _ ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
// #include "wiring.h"
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ii = pair<int,int>;
using iii = tuple<int,int,int>;
const int inf = 2e9+1;
const int mod = 1e9+7;
const int maxn = 3e5+100;
template<typename X, typename Y> bool ckmin(X& x, const Y& y) { return (y < x) ? (x=y,1):0; }
template<typename X, typename Y> bool ckmax(X& x, const Y& y) { return (x < y) ? (x=y,1):0; }
ll custo[maxn], pr[maxn], prmn[maxn], sufmn[maxn], dp[maxn];
ll min_total_length(vector<int>a,vector<int>b){
vector<pair<ll,bool>>v;
v.pb({-1,0});
for(auto x:a)v.pb({ll(x),0});
for(auto x:b)v.pb({ll(x),1});
sort(all(v));
int n = sz(a) + sz(b), l = 0, r = 0;
for(int i=1;i<=n;++i)pr[i] = pr[i-1] + v[i].first;
for(int i=1;i<=n;++i){
if(i!=1&&v[i].second!=v[i-1].second){
//calcula o intervalo anterior
l = r+1, r = i-1;
for(int j=r;j>=l;--j){
custo[j] = v[r].first*ll(r-j+1) - (pr[r] - pr[j-1]);
}
for(int j=l;j<=r;++j){
if(j==l)prmn[j] = custo[j] + dp[j-1] + (v[r+1].first-v[r].first);
else prmn[j] = min(prmn[j-1],
custo[j]+dp[j-1]+ll(r-j+1)*(v[r+1].first-v[r].first));
}
for(int j=r;j>=l;--j){
if(j==r)sufmn[j] = custo[j] + dp[j-1];
else sufmn[j] = min(sufmn[j+1],
custo[j]+dp[j-1]);
}
}
if(!l){
dp[i] = 1e18;
continue;
}
//agora, posso fazer o intervalo anterior vir ate mim,
//ou eu ir ate o intervalo anterior
int idx = max(l,2*r-i);//r - (i-r)
ll volta = pr[i] - pr[r] - ll(i-r)*v[r+1].first;
// eu ir ate o intervalo anterior
dp[i] = volta + sufmn[idx] + ll(i-r)*(v[r+1].first-v[r].first);
// cout<<volta<<" "<<idx<<" "<<dp[i]<<endl;
// intervalo anterior vir ate mim
if(2*r-i>l)ckmin(dp[i],volta+prmn[idx-1]);
// cout<<volta+prmn[idx]<<endl;
}
return dp[n];
}
int main(){
int n,m;cin>>n>>m;
vector<int>a(n), b(m);
for(auto& x:a)cin>>x;
for(auto& x:b)cin>>x;
cout<<min_total_length(a,b)<<endl;
}