Submission #1054510

#	Time	Username	Problem	Language	Result	Execution time	Memory
1054510		Unforgettablepl	Wiring (IOI17_wiring)	C++17	100 / 100	54 ms	10188 KiB

wiring

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

const long long INF = 1e15;

vector<long long> transformation(vector<int> idxa,vector<int> idxb,vector<long long> DPa) {
	int A = idxa.size()-1;
	int B = idxb.size()-1;
	vector DPres(B+1,INF);
	DPres[0]=DPa.back();
	if(A==0)return DPres;
	vector<long long> centerhelp(B+1);
	{
		// Center Outwards Transformation
		int lastA = idxa.back();
		long long sum = 0;
		long long curropt = INF;
		int otherIDX = A+1;
		for(int i=1;i<=B;i++) {
			otherIDX--;
			if(i<=A)sum+=idxb[i]-idxa[otherIDX];
			centerhelp[i]=sum;
			curropt+=idxb[i]-lastA;
			if(i<=A)curropt = min(curropt,min(DPa[otherIDX],DPa[otherIDX-1])+sum);
			DPres[i]=min(DPres[i],curropt);
		}
	}
	{
		// Inwards transformation
		long long sum = 0;
		long long curropt = INF;
		int cntCenterTransformation = min(A,B);
		idxb.erase(idxb.begin()+cntCenterTransformation+1,idxb.end());
		B = idxb.size()-1;
		int FirstB = idxb[1];
		long long base = centerhelp[B];
		long long lastOpt = INF;
		for(int i=A-B;i;i--) {
			base+=FirstB-idxa[i];
			lastOpt = min(lastOpt,min(DPa[i],DPa[i-1])+base);
			DPres[B]=min(DPres[B],min(DPa[i],DPa[i-1])+base);
		}
		for(int i=B;i;i--){
			int otherIDX = A+1-i;
			if(i==B) {
				curropt=min(curropt,lastOpt);
			} else {
				curropt+=FirstB-idxb[i+1];
			}
			curropt=min(curropt,min(DPa[otherIDX],DPa[otherIDX-1])+centerhelp[i]);
			DPres[i]=min(DPres[i],curropt);
		}
	}
	return DPres;
}

long long min_total_length(vector<int> r, vector<int> b) {
	vector<pair<int,int>> arr;
	for(int&i:b)arr.emplace_back(i,0);
	for(int&i:r)arr.emplace_back(i,1);
	sort(arr.begin(), arr.end());
	int n = arr.size();
	arr.insert(arr.begin(),{-1,0});
	arr.emplace_back(1e9+1,2);
	vector DPlast(1,0ll);
	vector lastidx(1,-1);
	vector curridx(1,-1);
	for(int i=1;i<=n;i++) {
		auto [idx,mycolour] = arr[i];
		curridx.emplace_back(idx);
		if(arr[i+1].second==mycolour)continue;
		DPlast = transformation(lastidx,curridx,DPlast);
		swap(curridx,lastidx);
		curridx.clear();
		curridx.emplace_back(-1);
	}
	return DPlast.back();
}

Compilation message (stderr)

wiring.cpp: In function 'std::vector<long long int> transformation(std::vector<int>, std::vector<int>, std::vector<long long int>)':
wiring.cpp:31:13: warning: unused variable 'sum' [-Wunused-variable]
   31 |   long long sum = 0;
      |             ^~~

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