Submission #137132

#	Time	Username	Problem	Language	Result	Execution time	Memory
137132		Mahdi_Jfri	Wiring (IOI17_wiring)	C++14	0 / 100	3 ms	1916 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];

vector<int> t[2];

long long min_total_length(std::vector<int> r, std::vector<int> b)
{
	int n = r.size() + b.size();
	vector<pair<int , int> > a;

	for(auto x : r)
		a.pb({x , 0});
	for(auto x : b)
		a.pb({x , 1});

	a.pb({-1e9 , -1});
	sort(a.begin() , a.end());

	memset(dp , 63 , sizeof dp);
	dp[0] = 0;
	for(int i = 1; i <= n; i++)
	{
		t[0].clear() , t[1].clear();
		for(int j = i - 1; j >= 0; j--)
		{
			t[a[j + 1].second].pb(a[j + 1].first);

			int shit = min(t[0].size() , t[1].size());
			if(shit == 1)
			{
				int ind = -1;
				if((int)t[0].size() == 1)
					ind = 0;
				else
					ind = 1;

				ll tmp = 0;
				for(auto x : t[ind ^ 1])
					tmp += abs(t[ind][0] - x);
				dp[i] = min(dp[i] , dp[j] + tmp);
			}
			if(t[0].size() == t[1].size())
			{
				ll tmp = 0;
				for(int j = 0; j < (int)t[0].size(); j++)
					tmp += abs(t[0][j] - t[1][j]);

				dp[i] = min(dp[i] , dp[j] + tmp);
			}
		}
	}

	return dp[n];
}

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