Submission #137185

#	Time	Username	Problem	Language	Result	Execution time	Memory
137185		Mahdi_Jfri	Wiring (IOI17_wiring)	C++14	100 / 100	95 ms	9704 KiB

wiring

#include "wiring.h"
#include<bits/stdc++.h>

using namespace std;

#define ll long long
#define pb push_back

const int maxn = 2e5 + 20;

ll dp[maxn] , mnp[maxn] , mns[maxn];

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

	int k = n + m;
	vector<pair<int , int> > a;
	for(auto x : r)
		a.pb({x , 0});
	for(auto x : b)
		a.pb({x , 1});

	sort(a.begin() , a.end());

	memset(dp , 63 , sizeof dp);
	dp[0] = 0;

	vector<int> lb;
	for(int i = 0; i < k; i++)
	{
		vector<int> nw;
		int j = i;
		while(j < k && a[j].second == a[i].second)
			nw.pb(j) , j++;

		if(!lb.empty())
		{
			int sz = lb.size() , shit = a[i].first - a[lb.back()].first;

			ll sum = 0;
			for(auto x : lb)
				sum += a[lb.back()].first - a[x].first;
			for(int j = 0; j < sz; j++)
			{
				dp[lb[j]] = min(dp[lb[j]] , dp[lb[j] + 1]);
				mnp[j] = dp[lb[j]] + 1LL * (sz - j) * shit + sum;
				if(j)
					mnp[j] = min(mnp[j] , mnp[j - 1]);

				sum -= a[lb.back()].first - a[lb[j]].first;
			}

			for(int j = sz - 1; j >= 0; j--)
			{
				sum += a[lb.back()].first - a[lb[j]].first;
				mns[j] = dp[lb[j]] + sum;
				if(j + 1 < sz)
					mns[j] = min(mns[j] , mns[j + 1]);
			}

			sum = 0;
			for(int x = i; x < j; x++)
			{
				sum += a[x].first - a[i].first;
				int s = x - i + 1;
				dp[x + 1] = min(dp[x + 1] , mns[max(sz - s , 0)] + 1LL * s * shit + sum);
				if(sz > s)
					dp[x + 1] = min(dp[x + 1] , mnp[sz - 1 - s] + sum);
			}
		}

		lb = nw;
		i = j - 1;
	}

	return dp[k];
}

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