제출 #452121

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
452121		jerzyk	Wiring (IOI17_wiring)	C++14	0 / 100	5 ms	7244 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;
	j = max(j, 1);
	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;
}

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];
		w = dp[i - 1].size() - 1;
		for(j = 1; j < (int)bl[i].size(); ++j)
		{
			dp[i][j] = dp[i - 1][w] + Price(i, j, w);
			while(w > 0 && dp[i - 1][w - 1] + Price(i, j, w - 1) <= dp[i][j])
			{
				--w;
				dp[i][j] = dp[i - 1][w - 1] + Price(i, j, w);
			}
		}
	}
	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(k);
}

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