제출 #1274297

#제출 시각아이디문제언어결과실행 시간메모리
1274297MisterReaperLet's Win the Election (JOI22_ho_t3)C++20
100 / 100
9 ms464 KiB
// File election.cpp created on 29.09.2025 at 20:44:48 #include <bits/stdc++.h> using i64 = long long; #ifdef DEBUG #include "/home/ahmetalp/Desktop/Workplace/debug.h" #else #define debug(...) void(23) #endif constexpr int inf = int(1E6); template<typename T> bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; } int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); std::cout << std::fixed << std::setprecision(9); int N, K; std::cin >> N >> K; std::vector<std::array<int, 2>> A(N); for (int i = 0; i < N; ++i) { std::cin >> A[i][0] >> A[i][1]; if (A[i][1] == -1) { A[i][1] = inf; } } std::sort(A.begin(), A.end(), [&](auto lhs, auto rhs) { return std::pair{lhs[1], lhs[0]} < std::pair{rhs[1], rhs[0]}; }); auto solve = [&](int x) -> double { std::vector<double> f(N + 1, inf), g(N + 1, inf); f[0] = 0; for (int k = 0; k < N; ++k) { std::vector<double> nf(N + 1, inf), ng(N + 1, inf); for (int j = 0; j <= std::min(k, K); ++j) { int i = k - j; if (i == x - 1) { chmin(ng[i + j + 1], f[j] + 1.d * A[k][1] / (i + 1)); } else { chmin(nf[j], f[j] + 1.d * A[k][1] / (i + 1)); } chmin(nf[j + 1], f[j] + 1.d * A[k][0] / (x + 1)); } for (int i = 0; i <= std::min(k, K); ++i) { chmin(ng[i], g[i]); chmin(ng[i + 1], g[i] + 1.d * A[k][0] / (x + 1)); } f = std::move(nf); g = std::move(ng); } return g[K]; }; double ans = 0; { auto B = A; std::sort(B.begin(), B.end()); for (int i = 0; i < K; ++i) { ans += B[i][0]; } debug(ans); } // for (int i = 1; i <= K; ++i) { // double res = solve(i); // debug(res); // ans = std::min(ans, res); // } int lo = 1, hi = K; while (lo <= hi) { int mid = (lo + hi) >> 1; double smid = solve(mid); double smidp = solve(mid + 1); ans = std::min({ans, smid, smidp}); if (smid > smidp) { lo = mid + 1; } else { hi = mid - 1; } } std::cout << ans << '\n'; return 0; }
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...