Submission #1070937

#	Time	Username	Problem	Language	Result	Execution time	Memory
1070937		oscar1f	Wiring (IOI17_wiring)	C++17	100 / 100	270 ms	99108 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,nbBloc;
vector<pair<ll,ll>> somTri;
vector<ll> valBloc[TAILLE_MAX];
vector<ll> cumuGau[TAILLE_MAX];
vector<ll> cumuDro[TAILLE_MAX];
unordered_map<ll,ll> memo,dv;

void afficher(vector<ll> v) {
    for (ll i:v) {
        cout<<i<<" ";
    }
    cout<<endl;
}

ll dyna(ll pos,ll pasFront,ll sens) {
    //cout<<"?"<<pos<<" "<<pasFront<<" "<<sens<<endl;
    if (pasFront<0) {
        return INFINI;
    }
    if (pos>nbBloc) {
        if (pasFront==0) {
            return 0;
        }
        return INFINI;
    }
    if (pasFront>(ll)valBloc[pos].size() and pasFront>(ll)valBloc[pos-1].size()) {
        return INFINI;
    }
    //cout<<"!"<<pos<<" "<<pasFront<<" "<<sens<<endl;
    ll caseTab=sens*TAILLE_MAX*TAILLE_MAX+pos*TAILLE_MAX+pasFront;
    if (dv[caseTab]!=0) {
        return memo[caseTab];
    }
    dv[caseTab]=1;
    ll ans=INFINI;
    if (sens==0) { // changer le sens
        ans=min(ans,dyna(pos,pasFront,1));
        if (pos>1) {
            ans=min(ans,dyna(pos,pasFront+1,0)-valBloc[pos-1].back()); //ajouter un passage de frontière
        }
    }
    else {
        ans=min(ans,dyna(pos,pasFront-1,1)+valBloc[pos][0]); //retirer un passage de frontière
    }
    if (pasFront<=(ll)valBloc[pos].size()) {
        ans=min(ans,cumuGau[pos][pasFront]-cumuDro[pos][valBloc[pos].size()-pasFront]+dyna(pos+1,valBloc[pos].size()-pasFront,0));
    }
    //cout<<pos<<" "<<pasFront<<" "<<sens<<" : "<<ans<<endl;
    memo[caseTab]=ans;
    return ans;
}

ll min_total_length(vector<int> r,vector<int> b) {
	nbRouge=r.size();
	nbBleu=b.size();
	for (ll i=0;i<nbRouge;i++) {
		somTri.push_back({r[i],0});
	}
	for (ll i=0;i<nbBleu;i++) {
		somTri.push_back({b[i],1});
	}
    sort(somTri.begin(),somTri.end());
    ll dern=2;
	for (auto i:somTri) {
        if (i.second==dern) {
            valBloc[nbBloc].push_back(i.first);
        }
        else {
            dern=i.second;
            nbBloc++;
            valBloc[nbBloc].push_back(i.first);
        }
    }
    ll somCour;
    for (ll i=1;i<=nbBloc;i++) {
        somCour=0;
        cumuGau[i].push_back(0);
        for (ll j:valBloc[i]) {
            somCour+=j;
            cumuGau[i].push_back(somCour);
        }
        somCour=0;
        cumuDro[i].push_back(0);
        for (ll j=(ll)valBloc[i].size()-1;j>=0;j--) {
            somCour+=valBloc[i][j];
            cumuDro[i].push_back(somCour);
        }
        /*afficher(valBloc[i]);
        afficher(cumuGau[i]);
        afficher(cumuDro[i]);
        cout<<endl;*/
    }
	return dyna(1,0,0);
}

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