Submission #337794

#	Time	Username	Problem	Language	Result	Execution time	Memory
337794		blue	전선 연결 (IOI17_wiring)	C++11	0 / 100	1088 ms	2668 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();
    //cout << n << ' ' << m << '\n';

    int rightend[m];
    for(int j = 0; j < m-1; j++) rightend[j] = j;
    rightend[m-1] = n-1;

    //cout << rightend[0] << '\n';

    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++)
    {
        //cout << r[i] << ' ' << abs(r[i] - b[0]) << '\n';
        res += abs(r[i] - b[0]);
    }
    for(int j = 1; 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