제출 #452124

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
452124		jerzyk	전선 연결 (IOI17_wiring)	C++14	100 / 100	98 ms	29684 KiB

wiring

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

using namespace std;
typedef long long ll;
const int N = 2 * 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);
	s1 = sum[p][i];
	s1 += bl[p][1] * max(0, (j - i));
	s2 = sum[p - 1][m] - sum[p - 1][m - j];
	s2 += bl[p - 1][m] * max(0, (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] || dp[i - 1][w] == I))
			{
				--w;
				dp[i][j] = dp[i - 1][w] + 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: 7 / 7
• Subtask 2: 13 / 13
• Subtask 3: 10 / 10
• Subtask 4: 25 / 25
• Subtask 5: 45 / 45