제출 #637346

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
637346		boris_mihov	Wiring (IOI17_wiring)	C++17	0 / 100	17 ms	2828 KiB

wiring

#include "wiring.h"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>
#include <set>

typedef long long llong;
const int MAXN = 1000 + 10;
const llong INF = 1e15;

int n, m;
llong r[MAXN];
llong b[MAXN];
llong val[MAXN];
bool bl[MAXN][MAXN];
llong dp[MAXN][MAXN];
llong f(int lPtr, int rPtr)
{
    if (lPtr == n && rPtr == m+1) return 0;
    if (lPtr != n && rPtr == m+1) return INF;
    if (bl[lPtr][rPtr]) return dp[lPtr][rPtr];

    bl[lPtr][rPtr] = true;
    dp[lPtr][rPtr] = INF;
    dp[lPtr][rPtr] = std::min(dp[lPtr][rPtr], f(lPtr, rPtr + 1) + val[rPtr]);
    if (lPtr != n) dp[lPtr][rPtr] = std::min(dp[lPtr][rPtr], f(lPtr + 1, rPtr + 1) + llabs(r[lPtr + 1] - b[rPtr]));
    return dp[lPtr][rPtr];
}

long long min_total_length(std::vector <int> R, std::vector <int> B) 
{
    if (R.size() > B.size()) std::swap(R, B);
    n = R.size();
    m = B.size();
    if (n == m)
    {
        exit(-1);
        llong ans = 0;
        for (int i = 0 ; i < n ; ++i)
        {
            ans += abs(R[i] - B[i]);
        }

        return ans;
    }
    for (int i = 1 ; i <= n ; ++i)
    {
        r[i] = R[i-1]; 
    }

    for (int i = 1 ; i <= m ; ++i)
    {
        b[i] = B[i-1]; 
    }

    int ptr = 1;
    for (int i = 1 ; i <= m ; ++i)
    {
        while (ptr + 1 <= n && r[ptr + 1] <= b[i]) ptr++;
        val[i] = abs(r[ptr] - b[i]);
        if (ptr + 1 <= n) val[i] = std::min(val[i], llabs(r[ptr + 1] - b[i]));
    }

	return f(1, 2) + llabs(r[1] - b[1]);
}

/*
9 7
12 23 29 53 62 77 89
10 21 32 34 39 40 58 67 81 

2 + 2 + 3 + 13 + 4 + 10 + 8 + 5 + 10 = 57...


*/

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