Advertisement
Guest User

Untitled

a guest
Jan 29th, 2020
118
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.82 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. typedef long double ld;
  6.  
  7. struct jeg
  8. {
  9. ld first;
  10. int second;
  11. };
  12.  
  13. const int N = 2000 + 7;
  14. int n;
  15. int a;
  16. int b;
  17. ld p1[N];
  18. ld p2[N];
  19. jeg best[N][N]; /// poz
  20.  
  21. bool bigger(jeg a, jeg b)
  22. {
  23. if (a.first != b.first)
  24. return a.first > b.first;
  25. else
  26. return a.second < b.second;
  27. }
  28.  
  29. jeg max(jeg a, jeg b)
  30. {
  31. if (bigger(a, b))
  32. return a;
  33. else
  34. return b;
  35. }
  36.  
  37. void compute(ld c)
  38. {
  39. for (int i = 1; i <= n; i++)
  40. {
  41. for (int x = 0; x <= a; x++)
  42. {
  43. jeg one;
  44. jeg two;
  45.  
  46. /// nu iau b
  47. /// nu iau a
  48. one = best[i - 1][x];
  49. /// iau a
  50. if (x >= 1)
  51. one = max(one, {best[i - 1][x - 1].first + p1[i], best[i - 1][x - 1].second});
  52.  
  53. /// iau b
  54. /// nu iau a
  55. two = {best[i - 1][x].first + c + p2[i], best[i - 1][x].second + 1};
  56. /// iau a
  57. if (x >= 1)
  58. two = max(two, {best[i - 1][x - 1].first + c + p2[i] + p1[i] - p1[i] * p2[i], best[i - 1][x].second + 1});
  59. if (x == 0)
  60. best[i][x] = one;
  61. else
  62. {
  63. best[i][x] = max(two, one);
  64. }
  65. }
  66. }
  67. }
  68.  
  69.  
  70. ld solve()
  71. {
  72. compute(0);
  73. /** for (int i = 1; i <= n; i++)
  74. {
  75. for (int x = 0; x <= a; x++)
  76. {
  77. cout << i << " " << x << " : " << best[i][x].first << "\n";
  78. }
  79. }
  80. exit(0);**/
  81. ld l = - (ld) 1e9;
  82. ld r = + (ld) 1e9;
  83. for (int i = 1; i <= 200; i++)
  84. {
  85. ld mid = (l + r) * 0.5;
  86. compute(mid);
  87. if (best[n][a].second <= b)
  88. l = mid;
  89. else
  90. r = mid;
  91. }
  92. compute(l);
  93. return {best[n][a].first - l * best[n][a].second};
  94. }
  95.  
  96. int main()
  97. {
  98. ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  99.  
  100. // freopen ("input", "r", stdin);
  101.  
  102. cin >> n >> a >> b;
  103. for (int i = 1; i <= n; i++)
  104. cin >> p1[i];
  105. for (int i = 1; i <= n; i++)
  106. cin >> p2[i];
  107. cout << fixed << setprecision(6) << solve() << "\n";
  108. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement