Submission #1087547

#TimeUsernameProblemLanguageResultExecution timeMemory
1087547I_am_Polish_GirlLet's Win the Election (JOI22_ho_t3)C++14
61 / 100
2599 ms2412 KiB
#include <vector> #include <algorithm> #include <map> #include <set> #include <unordered_map> #include <unordered_set> #include <stack> #include <queue> #include <cmath> #include <random> #include <chrono> #include <iomanip> #include <iostream> using namespace std; int log_ = 3; int inf = 200000000000000; int mod = 1102024631; int p = 505; bool cmp(pair <int, int> a, pair <int, int> b) { if (a.second < b.second) { return true; } return false; } double dp1[501][501]; vector <pair <int, int>> vp; int k; double c(int col) { int n = vp.size(); for (int i = 0; i <= n; i++) { for (int j = 0; j <= n; j++) { dp1[i][j] = inf; } } dp1[0][0] = 0; for (int k = 0; k < n; k++) { for (int i = n; i >= 0; i--) { for (int j = n; j >= 0; j--) { if (i > 0) { if (vp[k].second != -1) { dp1[i][j] = min(dp1[i][j], dp1[i - 1][j] + ((0. + vp[k].second) / i)); } } if (j > 0) { dp1[i][j] = min(dp1[i][j], dp1[i][j - 1] + ((0. + vp[k].first) / (col + 1))); } } } } double ans = inf; for (int i = 0; i <= n; i++) { for (int j = 0; j <= n; j++) { if (i + j == k) { if (i == col) { ans = min(dp1[i][j], ans); } } } } return ans; } mt19937 rnd(15); int rnd_(int l, int r) { int s = r - l + 1; int x = rnd(); x = abs(x); x %= (s + 1); return l + x; } signed main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int n; cin >> n >> k; vp.resize(n); for (int i = 0; i < n; i++) { int a, b; cin >> a >> b; vp[i] = { a, b }; } sort(vp.begin(), vp.end(), cmp); int l = 0; int r = n; for (int i = 0; i < n; i++) { if (vp[i].second == -1) r--; } r = min(r, k); while (r - l > 1) { int m = (l + r) /2; if (c(m) < c(m + 1)) r = m; else l = m+1; } double ans = inf; for (int i = l; i <= r; i++) { ans = min(c(i) , ans); } cout << fixed; cout << setprecision(9); cout << ans; }

Compilation message (stderr)

Main.cpp:20:11: warning: overflow in conversion from 'long int' to 'int' changes value from '200000000000000' to '552894464' [-Woverflow]
   20 | int inf = 200000000000000;
      |           ^~~~~~~~~~~~~~~
#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...