Submission #1249502

#	Time	Username	Problem	Language	Result	Execution time	Memory
1249502		nikd	Wiring (IOI17_wiring)	C++20	0 / 100	22 ms	7616 KiB

wiring

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

long long min_total_length(std::vector<int> r, std::vector<int> b) {
	int n = r.size()+b.size();
	//vector<ll> dp(n, -1);
	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<int>> 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);
	}
	dp[0][0] = 0;
	for(int i: seq[0]) dp[0][0] += seq[0].back()-i;
	for(int i = 1; i<seq.size()-1; i++){
		dp[i][0] = dp[i-1].back();
		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;
		};
		for(int j = seq[i-1].size()-1; 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);
		}
		ll sm = 0;
		for(int j = 1; j<dp[i].size(); j++){
			while(q.size() > 1 && c(q[0], j) >= c(q[1], j)) q.pop_front();
			sm += seq[i][j-1]-seq[i][0];
			dp[i][j] = c(q[0], j)+sm;
		}
		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];
		}
		int cc;
	}
	ll sol = LONG_LONG_MAX;
	int szl = seq.back().size();
	int last = dp.size()-2;
	ll delta = seq.back()[0]-seq[last].back();
	auto c2 = [&](array<ll, 2> arr, ll idx){
		return arr[0]+max(arr[1], idx)*delta;
	};
	for(int i = 0; i<dp[last].size()-1; i++){
		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: 0 / 7
• Subtask 2: 0 / 13
• Subtask 3: 0 / 10
• Subtask 4: 0 / 25
• Subtask 5: 0 / 45