제출 #753885

#제출 시각아이디문제언어결과실행 시간메모리
753885valerikk전선 연결 (IOI17_wiring)C++17
0 / 100
1076 ms5128 KiB
#include "wiring.h" #include <bits/stdc++.h> using namespace std; const long long INF = 2e18; long long getcost(vector<int> r, vector<int> b) { int n = r.size(); int m = b.size(); long long ret = 0; if (n < m) { for (int i = 0; i < n; ++i) { ret -= r[i]; } ret -= (m - n) * 1ll * r[n - 1]; for (int i = 0; i < m; ++i) { ret += b[i]; } } else { for (int i = 0; i < n; ++i) { ret -= r[i]; } ret += (n - m) * 1ll * b[0]; for (int i = 0; i < m; ++i) { ret += b[i]; } } return ret; } long long min_total_length(std::vector<int> r, std::vector<int> b) { int n = r.size(); int m = b.size(); vector<pair<int, int>> kek; for (int i = 0; i < n; ++i) { kek.push_back({r[i], 0}); } for (int i = 0; i < m; ++i) { kek.push_back({b[i], 1}); } sort(kek.begin(), kek.end()); vector<long long> dp(n + m + 1, INF); dp[0] = 0; for (int i = 0; i < n + m; ++i) { bool was = 0; vector<int> r1, b1; for (int j = i; j < n + m; ++j) { if (was) { if (kek[j].second == kek[i].second) { break; } } if (kek[j].second == kek[i].second) { r1.push_back(kek[j].first); } else { was = 1; b1.push_back(kek[j].first); } if (was) { long long cost = getcost(r1, b1); dp[j + 1] = min(dp[j + 1], dp[i] + cost); } } } return dp[n + m]; }
#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...