Submission #890440

#TimeUsernameProblemLanguageResultExecution timeMemory
890440arbuzickLet's Win the Election (JOI22_ho_t3)C++17
10 / 100
1 ms600 KiB
#include <bits/stdc++.h> using namespace std; void solve() { int n, k; cin >> n >> k; vector<int> a(n), b(n); vector<pair<int, int>> s_a, s_b; for (int i = 0; i < n; ++i) { cin >> a[i] >> b[i]; s_a.emplace_back(a[i], i); if (b[i] != -1) { s_b.emplace_back(b[i], i); } } sort(s_a.begin(), s_a.end()); sort(s_b.begin(), s_b.end()); long double ans = 1e9 + 7; for (int cnt_b = 0; cnt_b <= k && cnt_b <= (int)s_b.size(); ++cnt_b) { long double ans_nw = 0; vector<int> used(n); int speed = 1, cnt = 0; for (int i = 0; i < cnt_b; ++i) { ans_nw += s_b[i].first / (long double)speed; cnt++; speed++; used[s_b[i].second] = 1; } for (int i = 0; i < n; ++i) { if (cnt < k && !used[s_a[i].second]) { ans_nw += s_a[i].first / (long double)speed; cnt++; used[s_a[i].second] = 1; if (b[s_a[i].second] == s_a[i].first) { speed++; } } } ans = min(ans, ans_nw); } cout << ans << '\n'; } signed main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.precision(25); cout << fixed; int t = 1; // cin >> t; while (t--) { solve(); } 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...