Advertisement
Guest User

Untitled

a guest
Aug 2nd, 2024
94
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.24 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int N = 500;
  5. const double INF = 1e18;
  6.  
  7. int main() {
  8. ios::sync_with_stdio(0);
  9. cin.tie(0);
  10. int n, k;
  11. cin >> n >> k;
  12. static array<int, 2> p[N];
  13. for (int i = 0; i < n; i++) {
  14. int a, b;
  15. cin >> a >> b;
  16. if (b == -1) b = 1e9;
  17. p[i] = {b, a};
  18. }
  19. sort(p, p + n);
  20. static int g[N][N + 1];
  21. for (int i = 0; i < n; i++) {
  22. static int t[N];
  23. for (int j = i; j < n; j++) t[j - i] = p[j][1];
  24. sort(t, t + n - i);
  25. g[i][0] = 0;
  26. for (int j = 1; j <= n - i; j++) g[i][j] = g[i][j - 1] + t[j - 1];
  27. }
  28. double ans = g[0][k];
  29. for (int t = 0; t <= k; t++) {
  30. static double f[N + 1];
  31. for (int i = 0; i <= t; i++) f[i] = INF;
  32. f[0] = 0;
  33. for (int i = 0; i < n; i++) {
  34. for (int j = t; j >= 0; j--)
  35. f[j] = min(f[j] + (double)p[i][1] / (t + 1),
  36. j == 0 ? INF : f[j - 1] + (double)p[i][0] / j);
  37. if (k - i - 1 >= 0)
  38. ans = min(ans, f[t] + (double)g[i + 1][k - i - 1] / (t + 1));
  39. }
  40. }
  41. cout << fixed << setprecision(12) << ans << '\n';
  42. return 0;
  43. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement