# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
895226 | nightfal | Wiring (IOI17_wiring) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "wiring.h"
#include <stdlib.h>
#include <algorithm>
using namespace std;
long long min_total_length(std::vector<int> r, std::vector<int> b) {
int n = r.size(), m = b.size();
long long dp[n][m];
dp[0][0] = abs(r[0]-b[0]);
for(int i=1; i<n; i++)
dp[i][0] = dp[i-1][0] + abs(r[i]-b[0]);
for(int j=1; j<m; j++)
dp[0][j] = dp[0][j-1] + abs(r[0]-b[j]);
for(int i=1; i<n; i++)
for(int j=1; j<m; j++)
dp[i][j] = min(min(dp[i-1][j],dp[i][j-1]),dp[i-1][j-1])) + abs(r[i]-b[i]);
return dp[n-1][m-1];
}