Submission #1325601

#	Time	Username	Problem	Language	Result	Execution time	Memory
1325601		Faggi	Wiring (IOI17_wiring)	C++20	0 / 100	1089 ms	144828 KiB

wiring

#include <bits/stdc++.h>
#define ll long long
#define sz(x) int(x.size())
#define forn(i, n) for (i = 0; i < n; i++)
#define all(x) x.begin(), x.end()
#define pb push_back
#define mp make_pair
#define fr first
#define se second
using namespace std;

long long min_total_length(std::vector<int> r, std::vector<int> b)
{
    map<pair<ll, ll>, ll> dp;

    ll i = 0, j = 0, k, rec = 300, a, B, c, d, INF = LLONG_MAX, in;
    for(i=0; i<sz(r); i++)
        dp[{i,0}]=dp[{i-1,0}]+abs(r[i]-b[0]);
    for(i=0; i<sz(b); i++)
        dp[{0,i}]=dp[{0,i-1}]+abs(r[0]-b[i]);
    while (i < sz(r) || j < sz(b))
    {
        if (j < sz(b) && (i >= sz(r) || r[i] > b[j]))
        {
            in = max(0ll, i - rec);
            if(j!=0)
            {
                for (k = in; k <= i; k++)
                {
                    if (k != in)
                        a = dp[{k - 1, j}];
                    else
                        a=INF;
                    if (j > 0)
                    {
                        B = dp[{k - 1, j - 1}];
                        c = dp[{k, j - 1}];
                    }
                    else
                        c = B = INF;
                    dp[{k, j}] = min(a, min(B, c)) + abs(r[k] - b[j]);
                }
            }
            j++;
        }
        else
        {
            in = max(0ll, j - rec);
            if(i!=0)
            {
                for (k = in; k <= j; k++)
                {
                    if (k != in)
                        a = dp[{i, k - 1}];
                    else
                        a=INF;
                    if (i > 0)
                    {
                        B = dp[{i - 1, k}];
                        c = dp[{i - 1, k - 1}];
                    }
                    else
                        c = B = INF;
                    dp[{i,k}]=min(a,min(B,c))+abs(r[i]-b[k]);
                }
            }
            i++;
        }
    }
    return dp[{sz(r)-1,sz(b)-1}];
}

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