Submission #288851

#	Time	Username	Problem	Language	Result	Execution time	Memory
288851		luciocf	전선 연결 (IOI17_wiring)	C++14	0 / 100	28 ms	3596 KiB

wiring

#include <bits/stdc++.h>
#include "wiring.h"
 
#define ff first
#define ss second
 
using namespace std;
 
typedef pair<int, int> pii;
typedef long long ll;
 
const int maxn = 210;
const ll inf = 1e18+10;
 
int n, m;

pii a[maxn];

ll dp[maxn];
int opt[maxn];

ll pref[maxn];

int r[maxn], b[maxn];
 
ll min_total_length(vector<int> R, vector<int> B)
{
	n = R.size(), m = B.size();

	int aux = 0;

	for (auto i: R)
		a[++aux] = {i, 0};
	for (auto i: B)
		a[++aux] = {i, 1};

	sort(a+1, a+n+m+1);

	for (int i = 1; i <= n+m; i++)
		pref[i] = pref[i-1] + 1ll*a[i].ff;

	for (int i = 1; i <= n+m; i++)
		dp[i] = inf;

	int lastr = 0, lastb = 0;

	if (a[1].ss == 0) lastr = 1;
	else lastb = 1;

	for (int i = 2; i <= n+m; i++)
	{
		if (a[i].ss == a[i-1].ss)
		{
			opt[i] = opt[i-1];

			dp[i] = dp[i-1] + 1ll*a[i].ff;

			if (a[i].ss == 1)
			{
				if (i-lastr <= lastr-opt[i]+1) dp[i] -= 1ll*a[lastr+1].ff;
				else dp[i] -= (1ll*a[lastr].ff);
			}
			else
			{
				if (i-lastb <= lastb-opt[i]+1) dp[i] -= 1ll*a[lastb+1].ff;
				else dp[i] -= (1ll*a[lastb].ff);
			}
		}
		else
		{
			for (int j = i-1; j >= 1 && a[j].ss != a[i].ss; j--)
			{
				if (1ll*(i-j)*a[i].ff - 1ll*(pref[i-1]-pref[j-1]) + dp[j-1] <= dp[i])
				{
					dp[i] = 1ll*(i-j)*a[i].ff - 1ll*(pref[i-1]-pref[j-1]) + dp[j-1];
					opt[i] = j;
				}
			}
		}

		if (a[i].ss == 0) lastr = i;
		else lastb = i;
	}

	return dp[n+m];
}

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