Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define ll long long
- #define int ll
- #define pii pair<int, int>
- #define all(a) (a).begin(), a.end()
- #define rep(i, n) for (int i = 0; i < (n); ++i)
- #define pb push_back
- #define files(in, out) freopen(in, "r", stdin); freopen(out, "w", stdout)
- #define ff first
- #define ss second
- using namespace std;
- int sum(vector<int> &pref, int l, int r){
- if (l == 0) return pref[r];
- return pref[r] - pref[l - 1];
- }
- void solve(){
- int n, s;
- cin >> n >> s;
- vector<int> t(n), cost(n);
- vector<int> pref(n), pref_cost(n);
- rep(i, n){
- cin >> t[i];
- if (i == 0) pref[i] = t[i];
- else pref[i] = pref[i - 1] + t[i];
- }
- rep(i, n){
- cin >> cost[i];
- if (i == 0) pref_cost[i] = cost[i] * t[i];
- else pref_cost[i] = pref_cost[i - 1] + cost[i] * t[i];
- }
- int ans = 0;
- int time = 0;
- for (int i = 0; i < n; ++i){
- int l = i;
- int r = n;
- while (r - l > 1){
- int mid = (l + r) / 2;
- if (sum(pref, i, mid) <= s){
- l = mid;
- }
- else{
- r = mid;
- }
- }
- int plus = s - sum(pref, i, l);
- int mb_ans = sum(pref_cost, i, l);
- vector<pii> mbo;
- if (i > 0) mbo.pb({cost[i - 1], i - 1});
- if (l < n - 1) mbo.pb({cost[l + 1], l + 1});
- sort(all(mbo));
- reverse(all(mbo));
- for (auto el : mbo){
- int plus_time = min(plus, t[el.ss]);
- mb_ans += plus_time * cost[el.ss];
- plus -= plus_time;
- }
- ans = max(ans, mb_ans);
- }
- cout << ans;
- }
- signed main() {
- //files("moscow.in", "moscow.out");
- ios_base::sync_with_stdio(false);
- cin.tie(0);
- cout.tie(0);
- int t = 1;
- //cin >> t;
- while (t--) solve();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement