Submission #337789

#	Time	Username	Problem	Language	Result	Execution time	Memory
337789		blue	Wiring (IOI17_wiring)	C++11	0 / 100	1 ms	364 KiB

wiring

#include "wiring.h"
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <deque>
using namespace std;
 
long long min_total_length(vector<int> r, vector<int> b)
{
    if(r.size() < b.size()) swap(r, b);
    //assert(r.size() >= b.size());
 
    long long res = 0;
 
    int n = r.size(), m = b.size();
 
    int rightend[m];
    for(int j = 0; j < m-1; j++) rightend[j] = j;
    rightend[m-1] = n-1;
 
    for(int j = m-2; j >= 0; j--)
    {
        while(rightend[j+1] - rightend[j] > 1 && abs(r[rightend[j]+1] - b[j]) <= abs(r[rightend[j]+1] - b[j+1]))
            rightend[j]++;
    }
 
    for(int i = 0; i <= rightend[0]; i++) res += abs(r[i] - b[0]);
    for(int j = 0; j < m; j++)
    {
        for(int i = rightend[j-1]+1; i <= rightend[j]; i++) res += abs(r[i] - b[j]);
    }
    return res;
}

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