제출 #282968

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
282968		MKopchev	전선 연결 (IOI17_wiring)	C++14	17 / 100	1095 ms	7800 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);

    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],min(dp[i-1],dp[i])+add_left+between+add_right);
            }

            //cout<<j<<" -> "<<dp[j]<<endl;
        }

        start=j;
    }

    return dp[k];
}

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