| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 576175 | ogibogi2004 | 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 "wiring.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll INF=1e18;
struct bucket
{
bool col;
vector<ll> pos;
vector<ll> dp;
};
vector<bucket>v;
struct segment_tree
{
vector<ll>t;
int n;
void init(int sz)
{
n=sz;
t.resize(4*sz);
for(int i=0;i<4*sz;i++)t[i]=INF;
}
void update(int l,int r,int idx,int q,ll val)
{
if(l>q)return;
if(r<q)return;
if(l==r)
{
t[idx]=val;
return;
}
int mid=(l+r)/2;
update(l,mid,idx*2,q,val);
update(mid+1,r,idx*2+1,q,val);
t[idx]=min(t[idx*2],t[idx*2+1]);
}
void update(int idx,int val)
{
update(0,n,1,idx,val);
}
ll query(int l,int r,int idx,int ql,int qr)
{
if(l>qr)return INF;
if(r<ql)return INF;
if(l>=ql&&r<=qr)return t[idx];
int mid=(l+r)/2;
return min(query(l,mid,idx*2,ql,qr),query(mid+1,r,idx*2+1,ql,qr));
}
ll query(int l,int r)
{
return query(0,n,1,l,r);
}
};
long long min_total_length(vector<int> r, vector<int> b) {
vector<pair<ll,bool> >all;
for(ll i=0;i<r.size();i++)
{
all.push_back({r[i],0});
}
for(ll i=0;i<b.size();i++)
{
all.push_back({b[i],1});
}
sort(all.begin(),all.end());
bucket last;
last.col=all[0].second;
last.pos={all[0].first};
for(ll i=1;i<all.size();i++)
{
if(all[i].second==all[i-1].second)
{
last.pos.push_back(all[i].first);
}
else
{
v.push_back(last);
last.col=all[i].second;
last.pos={all[i].first};
}
}
v.push_back(last);
v[0].dp.push_back(0);
for(ll i=0;i<v[0].pos.size();i++)v[0].dp.push_back(INF);
/*for(int j=0;j<v[0].dp.size();j++)cout<<v[0].dp[j]<<" ";
cout<<endl;*/
for(ll i=1;i<v.size();i++)
{
vector<ll>prefmin(v[i-1].pos.size()+3,INF),sufmin(v[i-1].pos.size()+3,INF);
ll sufsum=0;
for(ll j=v[i-1].pos.size();j>=0;j--)
{
if(j!=v[i-1].pos.size())sufsum+=v[i-1].pos[j];
sufmin[j]=min((ll)sufmin[j+1],(ll)(v[i-1].dp[j]-sufsum+(v[i-1].pos.size()-j)*v[i-1].pos.back()));
}
ll prefsum=sufsum;
prefmin[0]=v[i-1].dp[0]-prefsum+v[i-1].pos.size()*v[i].pos[0];
for(ll j=1;j<=v[i-1].pos.size();j++)
{
prefsum-=v[i-1].pos[j-1];
prefmin[j]=min((ll)prefmin[j-1],(ll)(v[i-1].dp[j]-prefsum+(v[i-1].pos.size()-j)*v[i].pos[0]));
}
/*cout<<"prefmin : ";
for(int j=0;j<prefmin.size();j++)cout<<prefmin[j]<<" ";
cout<<endl;
cout<<"sufmin : ";
for(int j=0;j<sufmin.size();j++)cout<<sufmin[j]<<" ";
cout<<endl;*/
for(ll j=0;j<=v[i].pos.size();j++)v[i].dp.push_back(INF);
prefsum=0;
for(ll j=0;j<=v[i].pos.size();j++)
{
if(j!=0)prefsum+=v[i].pos[j-1];
// we will chose first j from this bucket
// connect them with last k from prev bucket
// first case : k <= j
// k=0,1,...j
// v[i].dp[j]=min(v[i].dp[j],sufmin[v[i-1].pos.size()-j]+prefsum+(j-k)*v[i].pos[0]);
//cout<<"^^ "<<j<<" "<<sufmin[max(0,(int)v[i-1].pos.size()-j)]+prefsum-j*v[i-1].pos.back()<<endl;
v[i].dp[j]=min(v[i].dp[j],sufmin[max(0,(ll)v[i-1].pos.size()-j)]+prefsum-j*v[i-1].pos.back());
//second case : k > j
// k = j+1,....,v[i-1].pos.size()
// v[i].dp[j]=min(v[i].dp[j],prefmin[v[i].pos-j-1]+prefsum-j*v[i-1].pos.back());
if((ll)(v[i-1].pos.size()-j-1)>=0)
{
v[i].dp[j]=min((ll)v[i].dp[j],(ll)(prefmin[v[i-1].pos.size()-j-1]+prefsum-j*v[i].pos[0]));
//cout<<"^^^ "<<j<<" "<<prefmin[v[i-1].pos.size()-j-1]+prefsum-j*v[i].pos[0]<<" "<<prefmin[v[i-1].pos.size()-j-1]<<" "<<prefsum<<" "<<j*v[i].pos[0]<<" "<<v[i-1].pos.size()-j-1<<endl;
}
}
//for(int j=0;j<v[i].dp.size();j++)cout<<v[i].dp[j]<<" ";
//cout<<endl;
}
//cout<<v.back().dp.back()<<endl;
return v.back().dp.back();
}