제출 #253876

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
253876		tinjyu	전선 연결 (IOI17_wiring)	C++14	100 / 100	51 ms	13432 KiB

wiring

#include "wiring.h"
#include <iostream>
using namespace std;
long long int sum[1000005],col[1000005],ri[1000005],le[1000005],num[1000005],dp[1000005],n,m;
long long min_total_length(std::vector<int> r, std::vector<int> b) {
	n=r.size();
	m=b.size();
	long long int pp=1,pa=0,pb=0;
	while(pa<n && pb<m)
	{
		if(r[pa]<b[pb])
		{
			num[pp]=r[pa];
			col[pp]=0;
			pa++;
		}
		else
		{
			num[pp]=b[pb];
			col[pp]=1;
			pb++;
		}
		pp++;
	}
	while(pa<n)
	{
		num[pp]=r[pa];
		col[pp]=0;
		pa++;
		pp++;
	}
	while(pb<m)
	{
		num[pp]=b[pb];
		col[pp]=1;
		pb++;
		pp++;
	}
	col[0]=col[1];
	col[n+m+1]=(col[n+m]+1)%2;
	long long int st=1,cnt=0,cnt1=0,len=0;
	for(int i=1;i<=n+m;i++)
	{
		if(col[i]!=col[i-1])
		{
			//cout<<" "<<i<<endl;
			sum[st]=num[st];
			for(int j=st+1;col[st]==col[j];j++)
			{
				sum[j]=sum[j-1]+num[j];
				//cout<<sum[j]<<" ";
			}
			//cout<<endl;
			for(int j=i-1;j>=st;j--)
			{
				ri[j]=num[i-1]*(i-j)-(sum[i-1]-sum[j-1])+min(dp[j],dp[j-1]);
				if(j!=i-1)ri[j]=min(ri[j],ri[j+1]);
				//cout<<ri[j]<<" ";
			}
			//cout<<endl;
			for(int j=st;j<i;j++)
			{
				le[j]=num[i]*(i-j)-(sum[i-1]-sum[j-1])+min(dp[j],dp[j-1]);
				if(j!=st)le[j]=min(le[j],le[j-1]);
				//cout<<le[j]<<" ";
			}
			//cout<<endl;
			sum[i-1]=0;
			st=i,cnt1=cnt,cnt=1;
			len=0;
		}
		else cnt++;
		if(st==1)
		{
			dp[i]=99999999999999999;
			continue;
		}
		len+=num[i]-num[st];
		long long int tmp=len;
		if(cnt>=cnt1)dp[i]=ri[st-cnt1]+cnt*(num[st]-num[st-1])+tmp;
		else dp[i]=min(ri[st-cnt]+cnt*(num[st]-num[st-1]),le[st-cnt-1])+tmp;
		//cout<<tmp<<" "<<num[i]<<" "<<col[i]<<" "<<dp[i]<<endl;
	}
	return dp[n+m];
}

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