Submission #757070

#	Time	Username	Problem	Language	Result	Execution time	Memory
757070		Rafi22	Wiring (IOI17_wiring)	C++14	100 / 100	220 ms	27204 KiB

wiring

#include <bits/stdc++.h>


using namespace std;

#define endl '\n'
#define st first
#define nd second
#define pb push_back
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define ll long long
ll mod=1000000007;
int inf=1000000007;
ll infl=100000000000000007;

const int N=200007,pot=1<<18;

ll seg[2*pot+7][3];
ll DP[N];
ll P[N],P1[N];
ll S[N],S1[N];

ll que(int v,int a,int b,int l,int r,int i)
{
    if(a<=l&&b>=r) return seg[v][i];
    if(r<a||l>b) return infl;
    return min(que(2*v,a,b,l,(l+r)/2,i),que(2*v+1,a,b,(l+r)/2+1,r,i));
}
void ins(int v,ll x,int i)
{
    v+=pot-1;
    seg[v][i]=x;
    while(v>1)
    {
        v/=2;
        seg[v][i]=min(seg[2*v][i],seg[2*v+1][i]);
    }
}

ll min_total_length(vector<int>r,vector<int>b)
{
    vector<pair<ll,int>>V;
    int n=sz(r),m=sz(b);
    for(int i=0;i<n;i++) V.pb({r[i],0});
    for(int i=0;i<m;i++) V.pb({b[i],1});
    sort(all(V));
    for(ll i=1;i<n+m;i++)
    {
        P[i]=P[i-1]+V[i].st-V[i-1].st;
        P1[i]=P1[i-1]+(V[i].st-V[i-1].st)*i;
    }
    for(int i=n+m-1;i>0;i--)
    {
        S[i]=S[i+1]+V[i].st-V[i-1].st;
        S1[i]=S1[i+1]+(V[i].st-V[i-1].st)*(n+m-i);
    }
    for(int i=1;i<2*pot;i++) seg[i][0]=infl,seg[i][1]=infl,seg[i][2]=infl;
    int L=1,R=0;
    ins(1,0,2);
    for(int i=0;i<n+m;i++)
    {
        if(i>0&&V[i].nd!=V[i-1].nd)
        {
            L=R+1;
            R=i;
            for(int j=L;j<=R;j++)
            {
                ll X=P1[R-1]-P1[j-1]-(P[R-1]-P[j-1])*(j-1);
                ll dp=que(1,j,i+1,1,pot,2);
                ins(j,dp+X,0);
                ins(j,dp+X+(V[R].st-V[R-1].st)*(R-j+1),1);
            }
        }
        DP[i+1]=infl;
        if(R>0)
        {
            ll k=i+1-R;
            ll X=S1[R+1]-S1[i+1]-(S[R+1]-S[i+1])*(n+m-i-1);
            DP[i+1]=min(DP[i+1],que(1,L,R-k+1,1,pot,1)+X);
            DP[i+1]=min(DP[i+1],que(1,max((ll)L,R-k+2),R,1,pot,0)+X+k*(V[R].st-V[R-1].st));
        }
        ins(i+2,DP[i+1],2);
    }
    return DP[n+m];
}
/*
ll min_total_length1(vector<int>r,vector<int>b)
{
    ll ans=0;
    for(int i=1;i<sz(r);i++) ans+=(ll)(r[i]-r[i-1])*i;
    for(int i=sz(b)-1;i>0;i--) ans+=(ll)(b[i]-b[i-1])*(sz(b)-i);
    ans+=(ll)max(sz(r),sz(b))*(ll)(b[0]-r.back());
    return ans;
}


int main()
{
    int n=100,m=200;
    cin>>n>>m;
    int t=0;
    vector<int>r,b;
    for(int i=0;i<n;i++)
    {
        t+=rand()%10+1;
        cin>>t;
        r.pb(t);
        cout<<t<<" ";
    }
    cout<<endl;
    for(int i=0;i<m;i++)
    {
        t+=rand()%10+1;
        cin>>t;
        b.pb(t);
        cout<<t<<" ";
    }
    cout<<endl;
    cout<<min_total_length(r,b)<<endl;
    return 0;
}*/

• Subtask 1: 7 / 7
• Subtask 2: 13 / 13
• Subtask 3: 10 / 10
• Subtask 4: 25 / 25
• Subtask 5: 45 / 45