제출 #612528

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
612528		MohamedAliSaidane	전선 연결 (IOI17_wiring)	C++14	7 / 100	27 ms	6088 KiB

wiring

#include <bits/stdc++.h>
    using namespace std;

    typedef long long ll;
    typedef double ld;
    typedef pair<int,int> pii;
    typedef pair<ll,ll> pll;

    typedef vector<int> vi;
    typedef vector<ll> vll;
    typedef vector<pii> vpi;
    typedef vector<pll> vpl;

    #define pb push_back
    #define popb pop_back
    #define all(x) (x).begin(),(x).end()

    #define ff first
    #define ss second

    const int nax = 205;
    const ll INF = 1e18;
    int n, m;
    vll A, B;
    ll dp[nax][nax];
    int f(int i, int j)
    {
        if(i >= n && j >= m)
            return 0ll;
        if(dp[i][j] != -1)
            return dp[i][j];
        ll br = INF, rb = INF, bt = INF ;
        if(j != 0 && i != n)
            br = f(i + 1,j) + abs(A[i] - B[j - 1]);
        if(i != 0 && j != n)
            rb = f(i, j + 1) + abs(A[i - 1] - B[j]);
        if(i != n && j != n)
            bt = f(i +1, j+ 1) + abs(A[i] - B[j]);

        return dp[i][j] = min(bt,min(rb, br));
    }
    ll min_total_length(vi r, vi b)
    {
        n = r.size(), m = b.size();
        sort(all(r));
        sort(all(b));
        for(auto e: r)
            A.pb(e);
        for(auto e: b)
            B.pb(e);
        memset(dp, -1,sizeof(dp));
        return f(0, 0);

    }

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