| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 520296 | new_acc | 전선 연결 (IOI17_wiring) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
#define ll long long
#define fi first
#define se second
using namespace std;
const int N=5e5+10;
ll dp[N];
int n;
ll t[N*3];
ll sp[N*3];
ll sum(int a,int b,int p,int k){
int mini=min(b-a+1,k-p+1);
return (sp[a+mini-1]-sp[a-1])-(sp[k]-sp[k-mini])+(b-a>k-p?sp[b]-sp[a+mini-1]-(t[k]*(ll)(b-a+1-mini)):t[a]*(ll)(k-p+1-mini)-(sp[k-mini]-sp[p-1]));
}
void divide(int a,int b,int l,int r,int p1,int p2){
if(b<a) return;
int sr=(a+b)/2;
int g=0;
ll res=LLONG_MAX;
for(int i=r;i>=l;i--){
ll s=sum(p1,sr,i,p2)+dp[i-1];
if(s<res) res=s,g=i;
}
dp[sr]=min(dp[p2]+sum(p1,sr,p2,p2),res);
divide(a,sr-1,g,r,p1,p2),divide(sr+1,b,l,g,p1,p2);
}
ll min_total_length(vector<int>r,vector<int>b){
vector<pair<int,bool> >v;
for(auto u:r) v.push_back({u,1});
for(auto u:b) v.push_back({u,0});
sort(v.begin(),v.end());
int wsk=0;
for(int i=0;i<(int)v.size();i++){
int a=v[i].se;
t[++wsk]=-1;
while(i<(int)v.size()&&v[i].se==a) t[++wsk]=v[i].fi,i++;
i--;
}
for(int i=1;i<=wsk;i++) sp[i]=sp[i-1]+(ll)t[i];
pair<int,int>l={0,0};
for(int i=2;i<=wsk;i++){
int j=i;
while(i<=wsk&&t[i]!=-1) i++;
i--;
if(l.fi==0) for(int k=j;k<=i;k++) dp[k]=(ll)1e16;
else{
divide(j,i,l.fi,l.se,j,l.se);
dp[j-1]=dp[l.se];
}
l={j,i};
i++;
}
return dp[wsk];
}
int main(){
vector<int>v1,v2;
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++){
int a;
cin>>a;
v1.push_back(a);
}
for(int i=1;i<=m;i++){
int a;
cin>>a;
v2.push_back(a);
}
cout<<min_total_length(v1,v2)<<"\n";
}