Submission #451852

#	Time	Username	Problem	Language	Result	Execution time	Memory
451852		jerzyk	Wiring (IOI17_wiring)	C++17	0 / 100	14 ms	14668 KiB

wiring

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

using namespace std;
typedef long long ll;
const int N = 100 * 1000 + 7;
const ll I = 1000000LL * 1000000LL * 500000LL;
pair<int, int> tab[N];
vector<ll> bl[N], dp[N], sum[N];

ll Price(int p, int i, int j)
{
	int m;
	ll s1, s2;
	ll w;
	m = bl[p - 1].size() - 1;
	j = m - j;
	if(j == i)
	{
		w = sum[p][i] - (sum[p - 1][m] - sum[p - 1][m - j]);
		return w;
	}
	if(j > i)
	{
		s1 = sum[p][i];
		s1 += bl[p][1] * (j - i);
		s2 = sum[p - 1][m] - sum[p - 1][m - j];
	}else
	{
		s1 = sum[p][i];
		s2 = sum[p - 1][m] - sum[p - 1][m - j];
		s2 += bl[p - 1][m] * (i - j);
	}
	w = s1 - s2;
	return w;
}

int TS(int v, int x)
{
	int p, s1, s2, k, i, wi;
	ll w1, w2;
	if(v == 2)
		return 0;
	p = 0;
	k = bl[v - 1].size() - 2;
	while(p + 2 < k)
	{
		s1 = p + (k - p) / 3;
		s2 = k - (k - p) / 3;
		w1 = Price(v, x, s1) + dp[v - 1][s1];
		w2 = Price(v, x, s2) + dp[v - 1][s2];
		if(w1 > w2)
			p = s1;
		else
			k = s2;
	}
	w1 = I;
	wi = 0;
	for(i = p; i <= k; ++i)
	{
		if(Price(v, x, i) + dp[v - 1][i] < w1)
		{
			w1 = Price(v, x, i) + dp[v - 1][i];
			wi = i;
		}
	}
	return wi;
}

ll Licz(int n)
{
	int i, j, w;
	for(i = 1; i < (int)dp[1].size(); ++i)
		dp[1][i] = I;
	for(i = 2; i <= n; ++i)
	{
		dp[i][0] = dp[i - 1][dp[i - 1].size() - 1];
		for(j = 1; j < (int)bl[i].size(); ++j)
		{
			w = TS(i, j);
			dp[i][j] = Price(i, j, w) + dp[i - 1][w];
			//cout << i << " " << j << " " << bl[i][j] << " " << dp[i][j] << "\n";
		}
	}
	return dp[n][dp[n].size() - 1];
}

ll min_total_length(vector<int> r, vector<int> b)
{
	int n, m, i, k;
	ll x;
	cin >> n >> m;
	n = r.size();
	m = b.size();
	for(i = 1; i <= n; ++i)
	{
		x = r[i - 1];
		tab[i] = make_pair(x, 0);
	}
	for(i = 1; i <= m; ++i)
	{
		x = b[i - 1];
		tab[i + n] = make_pair(x, 1);
	}
	n = n + m;
	sort(tab + 1, tab + 1 + n);
	k = 0;
	for(i = 1; i <= n; ++i)
	{
		if(tab[i].second != tab[i - 1].second || i == 1)
		{
			++k;
			bl[k].push_back(0);
			dp[k].push_back(0);
			sum[k].push_back(0);
		}
		bl[k].push_back(tab[i].first);
		dp[k].push_back(0);
		sum[k].push_back(tab[i].first);
		sum[k][sum[k].size() - 1] += sum[k][sum[k].size() - 2];
	}
	return Licz(n);
}

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