Submission #596844

#	Time	Username	Problem	Language	Result	Execution time	Memory
596844		franfill	Wiring (IOI17_wiring)	C++17	0 / 100	1 ms	300 KiB

wiring

#include "wiring.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

ll min_total_length(std::vector<int> r, std::vector<int> b) 
{
	int n = r.size() + b.size();
	vector < pair < int , int > > v;
	for (int x : r) v.emplace_back(x, 0);
	for (int x : b) v.emplace_back(x, 1);
	sort(v.begin(), v.end());
	vector < ll > pref(n, 0);
	vector < ll > dp(n, 1ll<<60);
	vector < ll > last(n, -1);

	pref[0] = v[0].first;
	for (int i = 1; i < n; i++)
	{
		auto [x, t] = v[i];
		pref[i] = pref[i-1] + x;
		if (v[i-1].second == t) last[i] = last[i-1];
		else last[i] = i-1;
		if (last[i] == -1) continue;

		dp[i] = dp[i-1] + v[i].first - v[last[i]].first;
		if (i - last[i] <= last[i] - last[last[i]])
		{
			//cerr << last[i] - (i - last[i]) << "\n";
			dp[i] = min(dp[i], (last[i] - (i-last[i]) >= 0 ? dp[last[i] - (i - last[i])] : 0) + (pref[i] - pref[last[i]]) - (pref[last[i]] - (last[i] - (i - last[i]) >= 0 ? pref[last[i] - (i - last[i])] : 0)));
		}
		//cerr << i << " " << dp[i] << "\n";
	}
	return dp[n-1];
}

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