Submission #283024

#	Time	Username	Problem	Language	Result	Execution time	Memory
283024		MKopchev	Wiring (IOI17_wiring)	C++14	13 / 100	59 ms	9848 KiB

wiring

#include "wiring.h"
#include<bits/stdc++.h>
using namespace std;

const int nmax=2e5+42;

int n,red[nmax],m,blue[nmax];

int k;
pair<int/*x*/,int/*type*/> inp[nmax];

long long dp[nmax];

long long pref_cost[nmax],suff_cost[nmax];

int pointer;
pair<long long,long long> lines[nmax];//ax+b

double meet(pair<long long,long long> u,pair<long long,long long> v)
{
    return 1.0*(v.second-u.second)/(u.first-v.first);
}
void push(long long a,long long b)
{
    while(pointer>=2&&meet(lines[pointer],{a,b})<=meet(lines[pointer-1],lines[pointer]))pointer--;

    pointer++;

    lines[pointer]={a,b};
}

long long query(int x)
{
    long long ret=1e18;

    for(int i=1;i<=pointer;i++)
        ret=min(ret,lines[i].first*x+lines[i].second);

    return ret;
}

long long min_total_length(std::vector<int> r, std::vector<int> b)
{
	n=r.size();
	m=b.size();

	for(int i=0;i<n;i++)
        red[i+1]=r[i];

    for(int j=0;j<m;j++)
        blue[j+1]=b[j];

    for(int i=1;i<=n;i++)
        inp[i]={red[i],0};

    for(int j=1;j<=m;j++)
        inp[n+j]={blue[j],1};

    k=n+m;

    sort(inp+1,inp+k+1);

    dp[0]=0;

    for(int i=1;i<=k;i++)dp[i]=1e18;

    int start=1;

    while(inp[start].second==inp[1].second)
    {
        dp[start]=1e18;
        start++;
    }

    while(start<=k)
    {
        pointer=0;

        long long add_right=0;

        int i_left=start-1;

        while(i_left>=1&&inp[i_left].second==inp[start-1].second)i_left--;

        i_left++;

        int j_right=start;

        while(j_right<=k&&inp[j_right].second==inp[start].second)j_right++;

        j_right--;

        for(int j=start+1;j<=j_right;j++)
            suff_cost[j]=suff_cost[j-1]+(inp[j].first-inp[start].first);

        for(int i=start-2;i>=i_left;i--)
            pref_cost[i]=pref_cost[i+1]+(inp[start-1].first-inp[i].first);
        /*
        cout<<"pref_cost ";for(int i=i_left;i<start;i++)cout<<pref_cost[i]<<" ";cout<<endl;
        cout<<"suff_cost ";for(int j=start;j<=j_right;j++)cout<<suff_cost[j]<<" ";cout<<endl;
        */

        //type 1 - j-start-1>=start-i

        long long mini=1e18;

        for(int j=start;j<=j_right;j++)
        {
            int i=2*start-j-1;

            if(i_left<=i)mini=min(mini,min(dp[i-1],dp[i])+pref_cost[i]);

            dp[j]=min(dp[j],mini+1LL*(j-start+1)*(inp[start].first-inp[start-1].first)+suff_cost[j]);

            //cout<<"type1 "<<j<<" "<<i<<" "<<dp[j]<<" "<<mini<<endl;
        }

        //type 2 - j-start-1<start-i

        int i=i_left;

        for(int j=j_right;j>=start;j--)
        {
            long long between=0;

            int i_now=2*start-j-2;

            while(i<=i_now)
            {
                push(i,pref_cost[i]+min(dp[i-1],dp[i]));
                //cout<<"type2 "<<j<<" "<<i<<" "<<dp[j]<<endl;
                i++;
            }

            dp[j]=min(dp[j],suff_cost[j]+1LL*(inp[start].first-inp[start-1].first)*start+query(inp[start-1].first-inp[start].first));
        }
        /*
        for(int p=start;p<=j_right;p++)
            cout<<p<<" -> "<<dp[p]<<endl;
        */
        start=j_right+1;
    }

    return dp[k];
}

Compilation message (stderr)

wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:124:23: warning: unused variable 'between' [-Wunused-variable]
  124 |             long long between=0;
      |                       ^~~~~~~
wiring.cpp:79:19: warning: unused variable 'add_right' [-Wunused-variable]
   79 |         long long add_right=0;
      |                   ^~~~~~~~~

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