Submission #427696

#	Time	Username	Problem	Language	Result	Execution time	Memory
427696		JeanBombeur	Wiring (IOI17_wiring)	C++17	100 / 100	63 ms	10088 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};
    for (int a : Rouges)
        Positions[nbBlocs ++] = {(long long)a, 0};
    for (int a : Bleus)
        Positions[nbBlocs ++] = {(long long)a, 1};
    if (Positions[0].second != Positions[1].second)
        Positions[0].second ^= 1;
    
    sort(Positions, Positions + nbBlocs);
    
    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