Submission #1046448

#	Time	Username	Problem	Language	Result	Execution time	Memory
1046448		ProtonDecay314	전선 연결 (IOI17_wiring)	C++17	0 / 100	1 ms	348 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;
    for(ll i = 0ll; i < rs; i++) {
        vll dpr(bs, 0ll);
        dp.pb(dpr);
    }

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

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

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