Submission #1046463

#	Time	Username	Problem	Language	Result	Execution time	Memory
1046463		ProtonDecay314	Wiring (IOI17_wiring)	C++17	7 / 100	114 ms	262144 KiB

wiring

// AM + DG

#include "wiring.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pi;
typedef pair<ll, ll> pll;
typedef vector<pi> vpi;
typedef vector<pll> vpll;
typedef vector<vpi> vvpi;
typedef vector<vpll> vvpll;
typedef vector<bool> vb;
#define IOS ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
#define L(varll, mn, mx) for(ll varll = (mn); varll < (mx); varll++)
#define LR(varll, mx, mn) for(ll varll = (mx); varll > (mn); varll--)
#define LI(vari, mn, mx) for(int vari = (mn); vari < (mx); vari++)
#define LIR(vari, mx, mn) for(int vari = (mx); vari > (mn); vari--)
#define INPV(varvec) for(auto& varveci : (varvec)) cin >> varveci
#define fi first
#define se second
#define pb push_back
#define INF(type) numeric_limits<type>::max()
#define NINF(type) numeric_limits<type>::min()
#define TCASES int t; cin >> t; while(t--)

ll min_total_length(vi r, vi b) {
    ll rs = r.size(), bs = b.size();
    vvll dp;
    const ll inf = 1'000'000'000'000ll;
    for(ll i = 0ll; i < rs; i++) {
        vll dpr(bs, inf);
        dp.pb(dpr);
    }

    for(ll ri = 0ll; ri < rs; ri++) {
        for(ll bi = 0ll; bi < bs; bi++) {
            if(ri == bi && bi == 0ll) dp[0ll][0ll] = abs(r[0ll] - b[0ll]);
            else if(bi == 0ll) dp[ri][0ll] = dp[ri - 1ll][0ll] + (ll)abs(r[ri] - b[0ll]);
            else if(ri == 0ll) dp[0ll][bi] = dp[0ll][bi - 1ll] + (ll)abs(r[0ll] - b[bi]);
            else {
                ll& ans = dp[ri][bi];
                ans = min(ans, (ll)abs(r[ri] - b[bi]) + dp[ri - 1ll][bi - 1ll]);
                ll min_r_conn = inf;
                ll min_b_conn = inf;

                for(ll i = bi + 1ll; i < bs; i++) min_b_conn = min(min_b_conn, (ll)abs(r[ri] - b[i]));
                for(ll i = ri + 1ll; i < rs; i++) min_r_conn = min(min_r_conn, (ll)abs(r[i] - b[bi]));
                
                ans = min(ans, min_b_conn + dp[ri - 1ll][bi]);
                ans = min(ans, min_r_conn + dp[ri][bi - 1ll]);
            }
        }
    }

	return dp[rs - 1ll][bs - 1ll];
}

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