Submission #1070713

#	Time	Username	Problem	Language	Result	Execution time	Memory
1070713		oscar1f	Wiring (IOI17_wiring)	C++17	0 / 100	146 ms	59900 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;
set<pair<ll,ll>> listeBleu,listeRouge;

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 INFINI;
	}
	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 (int i=0;i<nbRouge;i++) {
		posRouge.push_back(r[i]);
		listeRouge.insert({r[i],i});
	}
	for (int i=0;i<nbBleu;i++) {
		posBleu.push_back(b[i]);
		listeBleu.insert({b[i],i});
	}
	listeRouge.insert({-INFINI,-1});
	listeRouge.insert({INFINI,-1});
	listeBleu.insert({-INFINI,-1});
	listeBleu.insert({INFINI,-1});
	set<pair<ll,ll>>::iterator it;
	for (int i=0;i<nbRouge;i++) {
		it=listeBleu.lower_bound({posRouge[i],0});
		if ((*it).second!=-1) {
			memo[i*TAILLE_MAX+(*it).second]=-1;
		}
		it--;
		if ((*it).second!=-1) {
			memo[i*TAILLE_MAX+(*it).second]=-1;
		}
	}
	for (int i=0;i<nbBleu;i++) {
		it=listeRouge.lower_bound({posBleu[i],0});
		if ((*it).second!=-1) {
			memo[(*it).second*TAILLE_MAX+i]=-1;
		}
		it--;
		if ((*it).second!=-1) {
			memo[(*it).second*TAILLE_MAX+i]=-1;
		}
	}
	return dyna(0,0);
}

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