Advertisement
999ms

Untitled

Nov 7th, 2020
245
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.28 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. #define all(x) begin(x),end(x)
  3.  
  4. using namespace std;
  5. using ld = long double;
  6.  
  7. int main() {
  8. ios_base::sync_with_stdio(false);
  9. cin.tie(nullptr);
  10. cout.tie(nullptr);
  11. ld n, s;
  12. cin >> n >> s;
  13. ld ans = 0;
  14. vector<pair<ld,ld>> arr;
  15. for (int i = 0; i < n; i++) {
  16. ld a, b, c;
  17. cin >> a >> b >> c;
  18. if (c > 0) {
  19. ans += c;
  20. if (b > 0) {
  21. arr.push_back({a, b});
  22. }
  23. }
  24. }
  25. n = arr.size();
  26.  
  27. ld mn_val = 0;
  28.  
  29. for (auto& [x, y] : arr) {
  30. if (x == 0) {
  31. mn_val = max(mn_val, y);
  32. }
  33. }
  34.  
  35. ld left = mn_val;
  36. ld right = 1e9;
  37. ld mid;
  38. ld add = 0;
  39. for (int itr = 0; itr < 500; itr++) {
  40. mid = (left + right) / 2;
  41. ld used = 0;
  42. ld getted = 0;
  43. for (int i = 0; i < n; i++) {
  44. auto [a, b] = arr[i];
  45. // b + 2ax == mid
  46. // x = (mid - b) / (2a);
  47. if (a == 0) {
  48. continue;
  49. } else {
  50. ld x = (mid - b) / (2 * a);
  51. x = min(x, ld(-1) * b / 2 / a);
  52. if (x >= 0) {
  53. getted += a * x * x + b * x;
  54. used += x;
  55. }
  56. }
  57. }
  58. if (used <= s && mn_val > 0) {
  59. getted += mn_val * (s - used);
  60. }
  61. if (used <= s) {
  62. add = max(add, getted);
  63. }
  64. if (used > s) {
  65. left = mid;
  66. } else {
  67. right = mid;
  68. }
  69. }
  70.  
  71. ans += add;
  72.  
  73. cout << fixed << setprecision(15) << ans << '\n';
  74. }
  75.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement