이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define ll long long
#define db long double
#define N 100005
#define II pair <ll,ll>
#define III pair <ll,II>
#define IV pair <vector <int>,vector <int> >
#define IDB pair <db,int>
#define TII pair <treap*,treap*>
#define fst first
#define snd second
#define BIT(x,i) ((x>>i)&1)
#define pi acos(-1)
#define to_radian(x) (x*pi/180.0)
#define to_degree(x) (x*180.0/pi)
#define Log(x) (31-__builtin_clz((int)x))
#define LogLL(x) (63-__builtin_clzll((ll)x))
using namespace std;
#include "wiring.h"
II a[N];
ll f[N],n,i,j,k,Begin,sum[N],sub[N],l[N],r[N];
const ll oo=round(1e18);
ll min_total_length(vector <int> Red,vector <int> Blue)
{
for(int k:Red) a[++n]={ k,0 };
for(int k:Blue) a[++n]={ k,1 };
sort(a+1,a+n+1);
for(i=1;i<=n;i++)
{
if(i==1 || a[i].snd!=a[i-1].snd) Begin=i;
if(i==n || a[i].snd!=a[i+1].snd)
{
sum[Begin]=a[Begin].fst; l[Begin]=1;
for(j=Begin+1;j<=i;j++) sum[j]=sum[j-1]+a[j].fst,l[j]=j-Begin+1;
sub[i]=-a[i].fst; r[i]=1;
for(j=i-1;j>=Begin;j--) sub[j]=sub[j+1]-a[j].fst,r[j]=i-j+1;
}
}
for(i=1;i<=n;i++) f[i]=oo;
for(i=1;i<=n;i++)
{
if(i==1 || a[i].snd!=a[i-1].snd) Begin=i;
if(Begin>1 && (i==n || a[i].snd!=a[i+1].snd))
{
ll mi=oo;
for(j=Begin;j<=i;j++)
{
if(l[j]<=l[Begin-1])
{
k=Begin-l[j];
mi=min(mi,min(f[k],f[k-1])+sub[k]+a[Begin-1].fst*r[k]);
}
f[j]=min(f[j],mi+sum[j]-a[Begin-1].fst*l[j]);
}
mi=oo;
for(k=Begin-l[Begin-1];k<Begin;k++)
{
mi=min(mi,min(f[k],f[k-1])+sub[k]+a[Begin].fst*r[k]);
if(r[k]<=r[Begin])
{
j=Begin+r[k]-1;
f[j]=min(f[j],mi+sum[j]-a[Begin].fst*l[j]);
}
}
}
}
return f[n];
}
/*
int main()
{
freopen("wiring.inp","r",stdin);
freopen("wiring.out","w",stdout);
int n,m;
cin>>n>>m;
vector <int> r,b;
for(int i=1;i<=n;i++) cin>>k,r.push_back(k);
for(int i=1;i<=m;i++) cin>>k,b.push_back(k);
cout<<min_total_length(r,b);
}
*/
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |