Submission #637324

#	Time	Username	Problem	Language	Result	Execution time	Memory
637324		boris_mihov	Wiring (IOI17_wiring)	C++17	0 / 100	18 ms	2820 KiB

wiring

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

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

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

    bl[lPtr][rPtr][skip] = true;
    dp[lPtr][rPtr][skip] = INF;
    dp[lPtr][rPtr][skip] = std::min(dp[lPtr][rPtr][skip], f(lPtr, rPtr + 1, true) + abs(r[lPtr] - b[rPtr]));
    if (skip)
    {
        dp[lPtr][rPtr][skip] = std::min(dp[lPtr][rPtr][skip], f(lPtr + 1, rPtr, false));
    }

    return dp[lPtr][rPtr][skip];
}

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();
    for (int i = 1 ; i <= n ; ++i)
    {
        r[i] = R[i-1]; 
    }

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

	return f(1, 1, false);
}

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