제출 #393457

#제출 시각아이디문제언어결과실행 시간메모리
393457JimmyZJX전선 연결 (IOI17_wiring)C++14
7 / 100
34 ms6084 KiB
#include <iostream> #include <fstream> #include <algorithm> #include <cstring> #include <climits> #include <cassert> #include <tuple> #include <queue> #include <stack> #include <vector> #include <map> #include <set> #include <string> #include <unordered_set> #include <unordered_map> #include <numeric> using namespace std; typedef long long LL; typedef vector<int> Vi; typedef vector<LL> VL; typedef vector<bool> Vb; typedef vector<vector<int>> Vii; #define forR(i, n) for (int i = 0; i < (n); i++) LL dp[203][203]; LL min_total_length(Vi r, Vi b) { int n = r.size(), m = b.size(); LL sumR = 0, sumB = 0; forR(i, n) { sumR += abs(r[i] - b[0]); dp[i][0] = sumR; } forR(i, m) { sumB += abs(b[i] - r[0]); dp[0][i] = sumB; } for (int i = 1; i < n; i++) for (int j = 1; j < m; j++) { LL planA = abs(r[i] - b[j]) + dp[i - 1][j - 1]; int minI = INT_MAX; forR(k, m) minI = min(minI, abs(r[i] - b[k])); LL planB = minI + dp[i - 1][j]; int minJ = INT_MAX; forR(k, n) minJ = min(minJ, abs(r[k] - b[j])); LL planC = minJ + dp[i][j - 1]; dp[i][j] = min({ planA, planB, planC }); } return dp[n - 1][m - 1]; } #ifdef TEST_LOCAL int main() { auto r = min_total_length(Vi{ 1, 2, 3, 7 }, Vi{ 0, 4, 5, 9, 10 }); return 0; } #endif
#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...