Submission #1025708

#	Time	Username	Problem	Language	Result	Execution time	Memory
1025708		parsadox2	Wiring (IOI17_wiring)	C++17	100 / 100	40 ms	9932 KiB

wiring

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

#define F first
#define S second

using namespace std;

const int N = 2e5 + 10;
const long long inf = 1e18;
int a[N] , col[N] , n , prv[N] , opt[N];
long long dp[N] , psum[N];

long long Sum(int l , int r)
{
	return psum[r] - psum[l - 1];
}

long long Get(int l , int r)
{
	int mid = prv[r];
	if(mid <= l)
		return inf;
	int c1 = r - mid + 1 , c2 = mid - l;
	long long res = Sum(mid , r) - Sum(l , mid - 1);
	if(c1 >= c2)
		res -= 1LL * (c1 - c2) * a[mid - 1];
	else
		res += 1LL * (c2 - c1) * a[mid];
	return res;
}

void Solve(int id)
{
	int las = prv[id];
	if(las == 1)
	{
		dp[id] = inf;
		return;
	}
	int las2 = prv[las - 1];
	if(las2 == 1)
	{
		dp[id] = Get(1 , id);
		return;
	}
	if(las == id)
		opt[id] = las - 1;
	else
		opt[id] = opt[id - 1];
	dp[id] = Get(opt[id] , id) + min(dp[opt[id] - 1] , dp[opt[id]]);
	while(opt[id] != las2 && Get(opt[id] - 1 , id) + min(dp[opt[id] - 2] , dp[opt[id] - 1]) < dp[id])
	{
		dp[id] = Get(opt[id] - 1 , id) + min(dp[opt[id] - 2] , dp[opt[id] - 1]);
		opt[id]--;
	}
}

long long min_total_length(vector<int> r, vector<int> b) {
	n = r.size() + b.size();
	vector <pair<int , int>> vec;
	for(auto u : r)
		vec.push_back({u , 0});
	for(auto u : b)
		vec.push_back({u , 1});
	sort(vec.begin() , vec.end());
	for(int i = 1 ; i <= n ; i++)
	{
		a[i] = vec[i - 1].F;
		col[i] = vec[i - 1].S;
	}
	dp[0] = 0;
	prv[1] = 1;
	psum[1] = a[1];
	for(int i = 2 ; i <= n ; i++)
	{
		psum[i] = psum[i - 1] + a[i];
		prv[i] = (col[i] == col[i - 1] ? prv[i - 1] : i);
	}
	for(int i = 1 ; i <= n ; i++)
		Solve(i);
	return dp[n];
}

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