Submission #596855

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

wiring

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

ll pref[100];
int last[100];
ll dp[100];

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());

	pref[0] = v[0].first;
	dp[0] = 1ll<<60;
	last[0] = -1;
	for (int i = 1; i < n; i++)
	{
		dp[i] = 1ll<<60;
		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] = min(dp[i-1] + x - v[last[i]].first, dp[i]);
		if (i - last[i] <= last[i] - last[last[i]])
		{
			dp[i] = min(dp[i], dp[last[i] - (i - last[i])] + (pref[i] - pref[last[i]]) - (pref[last[i]] - pref[last[i] - (i - last[i])]));
		}
		/*if (last[last[i]] < last[i] - (i - last[i]) + 1) {
            dp[i] = min(dp[i], (pref[i] - pref[last[i]]) - (pref[last[i]] - pref[last[i] - (i - last[i])]) + dp[last[i] - (i - last[i])]);
        }*/
		//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