Submission #596905

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

wiring

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


ll min_total_length(std::vector<int> re, std::vector<int> bl) 
{
	int n = re.size() + bl.size();
	vector < pair < int , int > > v;
	for (int x : re) v.emplace_back(x, 0);
	for (int x : bl) v.emplace_back(x, 1);
	sort(v.begin(), v.end());

	ll cur = 0;
	vector < ll > dp(n), last(n);
	dp[0] = 1ll<<60;
	last[0] = -1;
	vector < ll > a(n, 0), b(n, 0);
	for (int i = 1; i < n; i++)
	{
		dp[i] = 1ll<<60;
		auto [x, t] = v[i];
		if (v[i-1].second == t) 
		{
			last[i] = last[i-1];
			cur += x - v[last[i]+1].first;
		}
		else 
		{
			cur = 0;
			last[i] = i-1;
			int siz = last[i] - last[last[i]];
			a[i-1] = 0;
			b[i-1] = x - v[i-1].first;
			for (int j = i-2; j > last[i-1]; j--)
			{
				a[j] = a[j+1] + v[i-1].first - v[j].first;
				b[j] = b[j+1] + v[i].first - v[j].first;
			}

			//cerr << "a: ";
			//for (auto v : a) cerr << v << " "; cerr << "\n";
			//cerr << "b: ";
			//for (auto v : b) cerr << v << " "; cerr << "\n";

			for (int j = i-1; j > max(last[i-1], 0ll); j--)
			{
				a[j] += dp[j-1];
				b[j] += dp[j-1];
			}
			//cerr << "da: ";
			//for (auto v : a) cerr << v << " "; cerr << "\n";
			//cerr << "db: ";
			//for (auto v : b) cerr << v << " "; cerr << "\n";
			for (int j = i-2; j > last[i-1]; j--)
			{
				a[j] = min(a[j], a[j+1]);
			}
			for (int j = last[i-1]+2; j < i; j++)
			{
				b[j] = min(b[j], b[j-1]);
			}
			//cerr << "ma: ";
			//for (auto v : a) cerr << v << " "; cerr << "\n";
			//cerr << "mb: ";
			//for (auto v : b) cerr << v << " "; cerr << "\n";
		}
		if (last[i] == -1) continue;
		int len = i - last[i];
		int gap = v[last[i]+1].first - v[last[i]].first;
		int split = max(last[last[i]]+1, last[i]-len+1);

		dp[i] = a[split] + gap*len;
		if (split != last[last[i]] + 1) dp[i] = min(dp[i], b[split-1]);
		dp[i] += cur;

		//cerr << i << ": " << split << " " << dp[i] << "\n";
		//cerr << "\n";
	}
	return dp[n-1];
}

Compilation message (stderr)

wiring.cpp: In function 'll min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:33:8: warning: unused variable 'siz' [-Wunused-variable]
   33 |    int siz = last[i] - last[last[i]];
      |        ^~~

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