Submission #427698

#	Time	Username	Problem	Language	Result	Execution time	Memory
427698		JeanBombeur	Wiring (IOI17_wiring)	C++17	100 / 100	68 ms	8476 KiB

wiring

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include "wiring.h"
using namespace std;

const long long INFINI = (1000 * 1000 * 1000);
const int MAX_BLOCS = (200 * 1000 + 1);

long long DP[MAX_BLOCS];
long long PrefixSum[MAX_BLOCS];

pair <long long, int> Positions[MAX_BLOCS];

int nbBlocs = 0;

long long min_total_length(vector<int> Rouges, vector<int> Bleus) {
    
    Positions[nbBlocs ++] = {- INFINI, 0};
    
    int szRouge = Rouges.size(), szBleus = Bleus.size();
    int gauche = 0, droite = 0;
    
    while (droite + gauche < szRouge + szBleus)
    {
        if (droite == szBleus || (gauche < szRouge && Rouges[gauche] < Bleus[droite]))
            Positions[nbBlocs ++] = {Rouges[gauche ++], 0};
        else
            Positions[nbBlocs ++] = {Bleus[droite ++], 1};
    }
    
    if (Positions[0].second != Positions[1].second)
        Positions[0].second ^= 1;
    
    for (int i = 1; i < nbBlocs; i ++)
    {
        PrefixSum[i] = PrefixSum[i - 1] + Positions[i].first;
    }
    
    int last = 1;
    
    for (int cur = 1; cur < nbBlocs; cur ++)
    {
        int next = cur;
        while (next < nbBlocs && Positions[cur].second == Positions[next].second)
            next ++;
        
        for (int i = last; i < cur; i ++)
        {
            DP[i] = min(DP[i], DP[i - 1] + Positions[cur].first - Positions[i].first);
        }
        
        long long coutTot = 0;
        long long mini = DP[cur - 1];
        
        for (int i = cur; i < next; i ++)
        {
            long long nb = i - cur + 1;
            coutTot += Positions[i].first - Positions[cur - 1].first;
            int prev = cur - 1 - nb;
            if (prev + 1 >= last)
            {
                mini = min(mini, DP[prev] + nb * Positions[cur - 1].first - PrefixSum[cur - 1] + PrefixSum[prev]);
            }
            DP[i] = coutTot + mini;
        }
        
        last = cur;
        cur = next - 1;
    }
    
	return DP[nbBlocs - 1];
}

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