Submission #1275923

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
 
int main(){
    int n;
    cin>>n;
    vector<long long int> a(n),b(n);
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    for(int i=0;i<n;i++) cin>>b[i];
    const long long int INF=1e15;
    vector<pair<long long int,long long int>> reach(n+1,{INF,-INF});
    reach[0]={0,0};
    long long int ma=b[0];
    for(int i=1;i<n+1;i++){
        int cost=reach[i-1].second;
;
        if(cost+a[i-1]>=0){
            reach[i]={reach[i-1].first+1,cost+a[i-1]};
        }
        else{
            if(ma==0){
                break;
            }
            int times=abs(cost+a[i-1])/ma+((cost+a[i-1])%ma!=0);
            reach[i]={reach[i-1].first+times+1,ma*times+cost+a[i-1]};
        }
        if(i==n) break;
        ma=max(ma,b[i]);
    }

    long long int res=0;
    ma=b[0];
    for(int i=0;i<=n;i++){
        if(reach[i].first<=n){
            long long int pl;
            pl=(n-reach[i].first)*ma;
            long long int val=reach[i].second;
            res=max(res,val+pl);
        }
        if(n-1<=i) continue;
        ma=max(ma,b[i+1]);
    }
    cout<<res<<endl;
    return 0;
}

Submission Info

Judge Result