Submission #585785

#TimeUsernameProblemLanguageResultExecution timeMemory
585785Drew_Let's Win the Election (JOI22_ho_t3)C++17
0 / 100
2222 ms316 KiB
#include <bits/stdc++.h> using namespace std; #define pb push_back #define mp make_pair #define f1 first #define s2 second #define fastio ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0); #define debug(x) cerr << "[" << #x << "]: " << x << "\n"; using ll = long long; using ld = long double; using ii = pair<int, int>; using pl = pair<ll, ll>; constexpr ld PI = 4*atan((ld)1); constexpr int MAX = 569; int n, k; ii a[MAX]; bool check(ld val) { int res = 0; ld pfx = 0, all = val; for (int i = -1; i < n; ++i) //the number of delegation { int ctr = i+1; if (i != -1) { if (all < a[i].s2 || a[i].s2 == -1) break; all -= a[i].s2; pfx += (ld)a[i].s2 / (i+1); all += val - pfx; } // debug(i); // debug(all); vector<int> v; for (int j = i+1; j < n; ++j) v.pb(a[j].f1); sort(v.begin(), v.end()); // cerr << "v: "; // for (int x : v) // cerr << x << ", "; // cerr << '\n'; ld rem = all; for (int x : v) if (rem >= x) rem -= x, ctr++; res = max(res, ctr); // debug(ctr); } // cerr << res << '\n'; return res >= k; } ld kn() { sort(a, a+n, [](const ii &x, const ii &y){ return (x.s2 == -1 ? 6969 : x.s2) < (y.s2 == -1 ? 6969 : y.s2); }); ld res = 1e18; for (int i = -1; i < n; ++i) { if (i != -1 && a[i].s2 == -1) break; ld ctr = 0; for (int j = 0; j <= i; ++j) ctr += (double)a[j].s2 / (j+1); for (int j = i+1; j < n; ++j) ctr += (double)a[j].f1 / (i+2); res = min(res, ctr); } return res; } int main() { fastio; cin >> n >> k; for (int i = 0; i < n; ++i) cin >> a[i].f1 >> a[i].s2; sort(a, a+n, [](const ii &x, const ii &y){ return (x.s2 == -1 ? 6969 : x.s2) < (y.s2 == -1 ? 6969 : y.s2); }); // check(11); // return 0; ld l = 0, r = 500000; for (int i = 0; i < 500; ++i) { ld mid = (l + r) / 2; if (check(mid)) r = mid; else l = mid; } cout << fixed << setprecision(15) << l << '\n'; cout << fixed << setprecision(15) << kn() << '\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...