Submission #919339

#	Time	Username	Problem	Language	Result	Execution time	Memory
919339		HuyQuang_re_Zero	Wiring (IOI17_wiring)	C++14	100 / 100	39 ms	14932 KiB

wiring

#include <bits/stdc++.h>
#define ll long long
#define db long double
#define N 200005
#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);
}
*/

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