Submission #365496

#	Time	Username	Problem	Language	Result	Execution time	Memory
365496		denkendoemeer	Wiring (IOI17_wiring)	C++14	0 / 100	1 ms	364 KiB

wiring

#include<bits/stdc++.h>
#include "wiring.h"
using namespace std;
#define ll long long
vector<pair<int,bool>>pct;
ll dp[200005],last[200005];
int t[200005],cnt[200005];
ll calc(int l,int r)
{
    int aux=t[r],st=r+1-aux,dr=aux-l;
    ll ans=last[r+1]-last[aux]-last[aux]+last[l];
    if (st>dr)
        ans=ans-1LL*(st-dr)*pct[aux-1].first;
    if (st<dr)
        ans=ans+1LL*(dr-st)*pct[aux].first;
    return ans;
}
ll min_total_length(vector<int>red,vector<int>blue)
{
    int n=blue.size(),m=red.size();
    int i;
    for(i=0;i<n;i++)
        pct.push_back(make_pair(blue[i],1));
    for(i=0;i<m;i++)
        pct.push_back(make_pair(red[i],0));
    sort(pct.begin(),pct.end());
    n=n+m;
    for(i=1;i<=n;i++)
        last[i]=last[i-1]+pct[i-1].first;
    ll *dp=&(::dp[1]);
    for(i=0;i<n;i++)
        dp[i]=2e17;
    int j;
    for(i=1;i<n;i++){
        t[i]=t[i-1];
        if (pct[i].second!=pct[i-1].second){
            int pre=t[i];
            t[i]=i;
            dp[i]=dp[i-1]+calc(i-1,i);
            cnt[i]=1;
            for(j=pre;j<i;j++)
                if (dp[i]>dp[j-1]+calc(j,i))
                    cnt[i]=i-j,dp[j]=dp[j-1]+calc(j,i);
        }
        else
            if (t[i]>0){
                cnt[i]=cnt[i-1];
                j=t[i]-cnt[i];
                if (cnt[i-1]==i-t[i])
                    if (j>t[j] && dp[j-1]+calc(j,i)>dp[j-2]+calc(j-1,i))
                        cnt[i]++,j--;
                dp[i]=min(dp[j],dp[j-1])+calc(j,i);
            }
    }
    return dp[n-1];
}

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