Submission #1218086

#TimeUsernameProblemLanguageResultExecution timeMemory
1218086shmax전선 연결 (IOI17_wiring)C++20
30 / 100
1098 ms15020 KiB
#include "wiring.h" #include <bits/stdc++.h> using namespace std; using i32 = int32_t; #define int long long #define inf 1000'000'000'000'000'000LL template<typename T> using vec = vector<T>; template<class T, class S> inline bool chmax(T &a, const S &b) { return (a < b ? a = b, 1 : 0); } template<class T, class S> inline bool chmin(T &a, const S &b) { return (a > b ? a = b, 1 : 0); } long long min_total_length(std::vector<i32> r, std::vector<i32> b) { vec<pair<int, int>> points; vec<vec<int>> cords(2, vec<int>()); for (int i: r) { points.emplace_back(i, 0); cords[0].emplace_back(i); } for (int i: b) { points.emplace_back(i, 1); cords[1].emplace_back(i); } sort(cords[0].begin(), cords[0].end()); sort(cords[1].begin(), cords[1].end()); sort(points.begin(), points.end()); int n = points.size(); vec<vec<int>> groups; for (int i = 0; i < n; i++) { if (i == 0 || points[i].second != points[i - 1].second) { groups.emplace_back(); } groups.back().emplace_back(points[i].first); } int m = groups.size(); vec<vec<int>> dp(m); vec<pair<int, int>> prev; prev = {{0, groups[0].size()}}; for (int t: groups[0]) { prev[0].first += groups[0].back() - t; } prev.emplace_back(inf, inf); for (int i = 1; i < m; i++) { dp[i].resize(groups[i].size() + 1, inf); int d = groups[i].front() - groups[i - 1].back(); int T = 0; { chmin(dp[i][0], prev.back().first); } for (int j = 1; j < dp[i].size(); j++) { T += groups[i][j - 1] - groups[i][0]; dp[i][j] = inf; for (int k = 0; k < prev.size() - (i == 1); k++) { int cost = prev[k].first + T + d * (max(j, (int) prev[k].second)); chmin(dp[i][j], cost); } } vec<pair<int, int>> new_prev; new_prev.emplace_back(dp[i].back(), 0); int P = 0; for (int j = dp[i].size() - 2; j >= 0; j--) { P += groups[i].back() - groups[i][j]; new_prev.emplace_back(dp[i][j] + P, dp[i].size() - j - 1); } reverse(new_prev.begin(), new_prev.end()); prev = new_prev; } return dp[m - 1].back(); }
#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...