| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 82303 | patcasrares | Wiring (IOI17_wiring) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<iostream>
#include<fstream>
#include<vector>
#define pb push_back
#define x first
#define y second
using namespace std;
ifstream fin("t.in");
ofstream fout("t.out");
const int DN=2e5+5;
long long n,m,ml[2][DN],poz1,poz2,nr,poz,l,f,urm,pr[DN],dp[DN];
long long s[DN],st,dr,mij1,mij2,val1,val2,val;
pair<int,int>r[DN];
vector<int>a,b;
long long ve(int st,int l,int dr)
{
long long val=dp[st-1],f=min(l-st+1,dr-l);
val+=1LL*r[l+1].x*f;
val-=s[st+f-1]-s[st-1];
val+=s[l+f]-s[l];
val-=1LL*r[l+1].x*f;
val+=1LL*(l-st+1-f)*r[l+1].x;
val-=s[l]-s[st+f-1];
val+=s[dr]-s[l+f];
val-=1LL*(dr-l-f)*r[l].x;
return val;
}
long long min_total_length(vector<int>a,vector<int>b)
{
n=a.size();
m=b.size();
poz1=poz2=0;
nr=n+m;
poz=-1;
f=0;
for(int i=0;i<=n+m;i++)
dp[i]=1e16;
while(nr--)
{
f++;
urm=1e18;
if(poz1==n)
{
r[f]={b[poz2],1};
poz2++;
}
else
if(poz2==m)
{
r[f]={a[poz1],0};
poz1++;
}
else
if(a[poz1]<b[poz2])
{
r[f]={a[poz1],0};
poz1++;
urm=b[poz2];
}
else
{
r[f]={b[poz2],1};
poz2++;
urm=a[poz1];
}
if(f==0)
continue;
if(r[f].y==r[f-1].y)
pr[f]=pr[f-1];
else
pr[f]=f-1;
}
for(int i=1;i<=f;i++)
s[i]=s[i-1]+r[i].x;
dp[0]=0;
for(int i=1;i<=f;i++)
{
if(pr[i]==0)
continue;
dr=pr[i];
st=pr[pr[i]]+1;
l=dr;
while(dr-st>200)
{
mij1=st+(dr-st)/3;
mij2=dr-(dr-st)/3;
val1=ve(mij1,l,i);
val2=ve(mij2,l,i);
if(val1<val2)
dr=mij2;
else
st=mij1;
}
val=1e16;
for(int j=st;j<=dr;j++)
val=min(val,ve(j,l,i));
dp[i]=val;
}
return dp[f];
}
int main()
{
}