# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
406734 | 2021-05-18T03:53:42 Z | 8e7 | Wiring (IOI17_wiring) | C++14 | 0 ms | 0 KB |
#include "wiring.h" //Challenge: Accepted #include <iostream> #include <algorithm> #include <vector> #include <utility> #define ll long long #define maxn 2005 #define pii pair<int, int> #define ff first #define ss second #define io ios_base::sync_with_stdio(0);cin.tie(0); using namespace std; ll dp[maxn][maxn]; ll ab(ll x) { return x > 0 ? x : -x; } const ll inf = 1LL<<60; long long min_total_length(std::vector<int> r, std::vector<int> b) { int n = r.size(), m = b.size(); /* for (int i = 0;i < n;i++) { for (int j = 0;j < m;j++) { dp[i][j] = inf; ll cost = ab(r[i] - b[j]); if (i == 0 && j == 0) dp[i][j] = cost; else if (!j) dp[i][j] = dp[i - 1][j] + cost; else if (!i) dp[i][j] = dp[i][j - 1] + cost; else { dp[i][j] = min(dp[i - 1][j], min(dp[i][j - 1], dp[i - 1][j - 1])) + cost; } } } return dp[n - 1][m - 1]; */ ll ans = 0; if (n > m) swap(n, m), swap(r, b); for (int i = 0;i < n;i++) ans += dis(r[i], b[i]); for (int i = n;i < m;i++) ans += dis(r[n - 1], b[i]); return ans; }