Submission #1249535

#	Time	Username	Problem	Language	Result	Execution time	Memory
1249535		nikd	Wiring (IOI17_wiring)	C++20	100 / 100	33 ms	11696 KiB

wiring

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

long long min_total_length(std::vector<int> r, std::vector<int> b) {
	//init seq e dp
	int n = r.size()+b.size();
	vector<pair<int, bool>> vec(n);
	int ii = 0;
	for(int j = 0; ii+j<n; ){
		if(ii==r.size()){
			vec[ii+j] = {b[j], 1}; j++;
		}
		else if(j == b.size()){
			vec[ii+j] = {r[ii], 0}; ii++;
		}
		else if(b[j] < r[ii]){
			vec[ii+j] = {b[j], 1};
			j++;
		}
		else{
			vec[ii+j] = {r[ii], 0};
			ii++;
		}
	}
	vector<vector<ll>> seq;
	vector<vector<ll>> dp;
	for(int i = 0; i<n; i++){
		seq.push_back({vec[i].first});
		dp.push_back({});
		while(i+1<n && vec[i].second == vec[i+1].second){
			seq.back().push_back(vec[i+1].first);
			i++;
		}
		dp.back().resize(seq.back().size()+1, -1);
	}

	//caso baso
	dp[0][0] = 0;
	for(int i: seq[0]) dp[0][0] += seq[0].back()-i;

	//sketch di sol
	//considero un intervallo uguale
	//una parte andrà a sx e una a dx
	//sx ][ dx 
	//l'unica eccezione è se ho uno da solo
	//in quel caso non cambia

	for(int i = 1; i<seq.size()-1; i++){
		dp[i][0] = dp[i-1].back(); //non prendo niente da prima
		ll delta = seq[i][0]-seq[i-1].back();
		deque<array<ll, 2>> q;
		auto c = [&](array<ll, 2> arr, ll idx){
			return arr[0]+max(arr[1], idx)*delta;
		};
		//aumentano i valori più piccoli -> li metto per prima
		for(int j = seq[i-1].size(); j>=0; j--){
			if(dp[i-1][j] == -1) continue;
			array<ll, 2> nw = {dp[i-1][j], (ll)seq[i-1].size()-j};
			ll cost = c(nw, 1);
			while(q.size() && cost <= c(q.back(), 1)) q.pop_back();
			q.push_back(nw);
		}
		array<ll, 2> curr_min = q.front(); 
		q.pop_front();
		//calcolo dp (vero sx)
		ll sm = 0;
		for(int j = 1; j<dp[i].size(); j++){
			if(q.size() && c(curr_min, j) >= c(q[0], j)){
				curr_min = q[0];
				q.pop_front();
			}
			if(q.size() && q[0][1] <= j) q.pop_front();
			sm += seq[i][j-1]-seq[i][0];
			dp[i][j] = c(curr_min, j)+sm;
		}
		//conntributo a destra
		sm = 0;
		for(int j =dp[i].size()-2; j>=0; j--){
			if(dp[i][j] != -1) dp[i][j] += sm;
			if(j> 0) sm += seq[i].back()-seq[i][j-1];
		}
	}
	ll sol = LONG_LONG_MAX;
	int szl = seq.back().size();
	int last = dp.size()-2;
	ll dlet = seq.back()[0]-seq[last].back();
	auto c2 = [&](array<ll, 2> arr, ll idx){
		return arr[0]+max(arr[1], idx)*dlet;
	};
	for(int i = 0; i<dp[last].size(); i++){
		if(dp[last][i] == -1) continue;
		sol = min(sol, c2({dp[last][i], (ll)seq[last].size()-i}, szl));
	}
	for(int i = seq.back().size()-1; i>0; i--){
		sol += seq.back()[i]-seq.back()[0];
	}
	return sol;
}

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