Advertisement
Guest User

Untitled

a guest
Dec 7th, 2019
138
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.86 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. #define ll long long
  4. #define int ll
  5. #define pii pair<int, int>
  6. #define all(a) (a).begin(), a.end()
  7. #define rep(i, n) for (int i = 0; i < (n); ++i)
  8. #define pb push_back
  9. #define files(in, out) freopen(in, "r", stdin); freopen(out, "w", stdout)
  10. #define ff first
  11. #define ss second
  12.  
  13. using namespace std;
  14.  
  15. int sum(vector<int> &pref, int l, int r){
  16. if (l == 0) return pref[r];
  17. return pref[r] - pref[l - 1];
  18. }
  19.  
  20. void solve(){
  21. int n, s;
  22. cin >> n >> s;
  23. vector<int> t(n), cost(n);
  24. vector<int> pref(n), pref_cost(n);
  25. rep(i, n){
  26. cin >> t[i];
  27. if (i == 0) pref[i] = t[i];
  28. else pref[i] = pref[i - 1] + t[i];
  29. }
  30. rep(i, n){
  31. cin >> cost[i];
  32. if (i == 0) pref_cost[i] = cost[i] * t[i];
  33. else pref_cost[i] = pref_cost[i - 1] + cost[i] * t[i];
  34. }
  35. int ans = 0;
  36. int time = 0;
  37. for (int i = 0; i < n; ++i){
  38. int l = i;
  39. int r = n;
  40. while (r - l > 1){
  41. int mid = (l + r) / 2;
  42. if (sum(pref, i, mid) <= s){
  43. l = mid;
  44. }
  45. else{
  46. r = mid;
  47. }
  48. }
  49. int plus = s - sum(pref, i, l);
  50. int mb_ans = sum(pref_cost, i, l);
  51. vector<pii> mbo;
  52. if (i > 0) mbo.pb({cost[i - 1], i - 1});
  53. if (l < n - 1) mbo.pb({cost[l + 1], l + 1});
  54. sort(all(mbo));
  55. reverse(all(mbo));
  56. for (auto el : mbo){
  57. int plus_time = min(plus, t[el.ss]);
  58. mb_ans += plus_time * cost[el.ss];
  59. plus -= plus_time;
  60. }
  61. ans = max(ans, mb_ans);
  62. }
  63. cout << ans;
  64. }
  65.  
  66. signed main() {
  67. //files("moscow.in", "moscow.out");
  68. ios_base::sync_with_stdio(false);
  69. cin.tie(0);
  70. cout.tie(0);
  71. int t = 1;
  72. //cin >> t;
  73. while (t--) solve();
  74. return 0;
  75. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement