Submission #282958

#	Time	Username	Problem	Language	Result	Execution time	Memory
282958		MKopchev	Wiring (IOI17_wiring)	C++14	0 / 100	1089 ms	5880 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 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);

    /*
    long long outp=0;

    for(int i=1;i<n;i++)
        outp+=1LL*i*(red[i+1]-red[i]);

    for(int i=1;i<m;i++)
        outp+=1LL*(m-i)*(blue[i+1]-blue[i]);

    outp+=1LL*max(n,m)*(blue[1]-red[n]);
    */

    dp[0]=0;

    int start=1;

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

    while(start<=k)
    {
        int j;
        for(j=start;j<=k&&inp[j].second==inp[start].second;j++)
        {
            dp[j]=1e18;

            long long add_right=0;

            for(int p=start;p<j;p++)
                add_right+=1LL*(inp[p+1].first-inp[p].first)*(j-p);

            long long add_left=0,between=0;

            for(int i=start-1;i>=1&&inp[start-1].second==inp[i].second;i--)
            {
                add_left+=(inp[start-1].first-inp[i].first);

                between=1LL*(inp[start].first-inp[start-1].first)*max(j-start+1,start-i);

                dp[j]=min(dp[j],dp[i-1]+add_left+between+add_right);
            }
        }

        start=j;
    }

    return dp[k];
}

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