제출 #377685

#제출 시각아이디문제언어결과실행 시간메모리
377685SortingWiring (IOI17_wiring)C++17
7 / 100
33 ms5612 KiB
#include "wiring.h"
#include <bits/stdc++.h>

typedef long long ll;
using namespace std;

template<typename T> void check_min(T &a, const T b){a = (a < b) ? a : b;}
const int N = 200 + 3;
const ll INF = 1e18;

ll dp[N][N];

ll min_total_length(vector<int> r, vector<int> b) {
	dp[r.size()][b.size()] = 0;
    for(int j = (int)b.size() - 1; j >= 0; --j)
        dp[r.size()][j] = INF;

    for(int i = (int)r.size() - 1; i >= 0; --i){
        dp[i][b.size()] = INF;
        for(int j = (int)b.size() - 1; j >= 0; --j){
            dp[i][j] = INF;
            check_min(dp[i][j], dp[i + 1][j + 1] + abs(r[i] - b[j]));
            check_min(dp[i][j], dp[i + 1][j] + abs(r[i] - b[j]));
            check_min(dp[i][j], dp[i][j + 1] + abs(r[i] - b[j]));
        }
    }
    return dp[0][0];
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...