Submission #328259

#	Time	Username	Problem	Language	Result	Execution time	Memory
328259		arnold518	Wiring (IOI17_wiring)	C++14	100 / 100	61 ms	19936 KiB

wiring

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

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 2e5;
const ll INF = 1e18;

int N;
pll A[MAXN+10];
ll L[MAXN+10], R[MAXN+10];
ll L2[MAXN+10], R2[MAXN+10];
ll L3[MAXN+10], R3[MAXN+10];
ll dp[MAXN+10];

ll min_total_length(vector<int> _R, vector<int> _B)
{
	N=_R.size()+_B.size();
	for(int i=0; i<_R.size(); i++) A[i+1]={_R[i], 0};
	for(int i=0; i<_B.size(); i++) A[i+_R.size()+1]={_B[i], 1};

	sort(A+1, A+N+1);

	A[0]=A[1];
	A[N+1]=A[N];
	
	pll bef={-1, -1};
	for(int i=1; i<=N; i++)
	{
		if(bef.second!=A[i].second)
		{
			bef=A[i];
			L2[i]=A[i].first-A[i-1].first;
			L3[i]=1;
		}
		else
		{
			L[i]+=L[i-1];
			L2[i]=L2[i-1];
			L3[i]=L3[i-1]+1;
		}
		L[i]+=A[i].first-bef.first;
	}

	bef={-1, -1};
	for(int i=N; i>=1; i--)
	{
		if(bef.second!=A[i].second)
		{
			bef=A[i];
			R2[i]=A[i+1].first-A[i].first;
			R3[i]=1;
		}
		else
		{
			R[i]+=R[i+1];
			R2[i]=R2[i+1];
			R3[i]=R3[i+1]+1;
		}
		R[i]+=bef.first-A[i].first;
	}

	for(int i=1; i<=N; i++) dp[i]=INF;
	dp[0]=0;

	vector<ll> V1, V2;
	for(int i=1; i<=N;)
	{
		int col=A[i].second;
		int l=i, r=i;
		for(; i<=N && A[i].second==col; i++) r=i;

		if(!V1.empty())
		{
			for(int j=l; j<=r; j++)
			{
				int t=j-l;

				dp[j]=min(dp[j], L[j]+L3[j]*L2[j]+V2[min((int)V2.size()-1, t)]);
				if(t<V1.size()) dp[j]=min(dp[j], L[j]+V1[t]);
			}
		}

		V1.clear(); V2.clear();
		for(int j=l; j<=r; j++)
		{
			V1.push_back(min(dp[j], dp[j-1])+R3[j]*R2[j]+R[j]);
			V2.push_back(min(dp[j], dp[j-1])+R[j]);
		}
		for(int j=1; j<V1.size(); j++) V1[j]=min(V1[j-1], V1[j]);
		for(int j=V1.size()-2; j>=0; j--) V2[j]=min(V2[j+1], V2[j]);
		reverse(V1.begin(), V1.end());
		reverse(V2.begin(), V2.end());
	}
	return dp[N];
}

Compilation message (stderr)

wiring.cpp: In function 'll min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:22:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |  for(int i=0; i<_R.size(); i++) A[i+1]={_R[i], 0};
      |               ~^~~~~~~~~~
wiring.cpp:23:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |  for(int i=0; i<_B.size(); i++) A[i+_R.size()+1]={_B[i], 1};
      |               ~^~~~~~~~~~
wiring.cpp:83:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |     if(t<V1.size()) dp[j]=min(dp[j], L[j]+V1[t]);
      |        ~^~~~~~~~~~
wiring.cpp:93:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |   for(int j=1; j<V1.size(); j++) V1[j]=min(V1[j-1], V1[j]);
      |                ~^~~~~~~~~~

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