Submission #137175

#	Time	Username	Problem	Language	Result	Execution time	Memory
137175		Mahdi_Jfri	Wiring (IOI17_wiring)	C++14	17 / 100	1065 ms	7144 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];

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;
	for(int i = 0; i < k; i++)
	{
		int j = i;
		while(j >= 0 && a[j].second == a[i].second)
			j--;

		if(j < 0)
			continue;

		ll sum = 0;
		for(int x = j + 1; x <= i; x++)
			sum += a[x].first - a[j + 1].first;

		int sz2 = i - j;
		int x = j;
		while(x >= 0 && a[x].second == a[j].second)
		{
			ll sum = 0;
			for(int ind = x; ind <= j; ind++)
				sum += a[j].first - a[ind].first;
			for(int ind = j + 1; ind <= i; ind++)
				sum += a[ind].first - a[j + 1].first;

			int sz1 = j - x + 1 , sz2 = i - j;
			sum += 1LL * (a[j + 1].first - a[j].first) * max(sz1 , sz2);
			dp[i + 1] = min(dp[i + 1] , min(dp[x + 1] , dp[x]) + sum);
			x--;
		}
	}

	return dp[k];
}

Compilation message (stderr)

wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:41:7: warning: unused variable 'sz2' [-Wunused-variable]
   int sz2 = i - j;
       ^~~

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