Submission #1070697

#	Time	Username	Problem	Language	Result	Execution time	Memory
1070697		oscar1f	Wiring (IOI17_wiring)	C++17	7 / 100	1069 ms	262144 KiB

wiring

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

using ll=long long;

const ll TAILLE_MAX=100*1000+5,INFINI=(ll)1000*1000*1000*1000*1000;
ll nbRouge,nbBleu;
vector<ll> posBleu,posRouge;
unordered_map<ll,ll> memo;

ll dyna(ll idRouge,ll idBleu) {
	if (idRouge==nbRouge and idBleu==nbBleu) {
		return 0;
	}
	if (idRouge==nbRouge or idBleu==nbBleu) {
		return INFINI;
	}
	ll caseTab=idRouge*TAILLE_MAX+idBleu;
	ll ans=memo[caseTab];
	if (ans!=0) {
		return ans;
	}
	ans=abs(posRouge[idRouge]-posBleu[idBleu])+min(min(dyna(idRouge,idBleu+1),dyna(idRouge+1,idBleu)),dyna(idRouge+1,idBleu+1));
	memo[caseTab]=ans;
	//cout<<idRouge<<" "<<idBleu<<" : "<<ans<<endl;
	return ans;
}

ll min_total_length(vector<int> r,vector<int> b) {
	nbRouge=r.size();
	nbBleu=b.size();
	for (auto i:r) {
		posRouge.push_back(i);
	}
	for (auto i:b) {
		posBleu.push_back(i);
	}
	return dyna(0,0);
}

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