Submission #1275871

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
 
int main(){
    int n;
    cin>>n;
    vector<int> a(n),b(n);
    vector<int> asum(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=1e10;
    vector<pair<long long int,int>> reach(n+1,{INF,INF});
    reach[0]={0,0};
    int ma=b[0];
    for(int i=1;i<n+1;i++){
        asum[i-1]+=a[i-1];
        int cost=reach[i-1].second;
        if(cost+a[i]>=0){
            reach[i]={reach[i].first+1,cost+a[i]};
        }
        else{
            if(ma==0){
                break;
            }
            int times=(cost+a[i])/ma+((cost+a[i])%ma==0);
            reach[i]={reach[i].first+times,ma*times+cost+a[i]};
        }
        if(i==n) break;
        ma=max(ma,b[i]);
    }
    long long int res=0;
    for(int i=0;i<n;i++){
        if(reach[i].first<=n){
            res=max(res,reach[i].second+(n-reach[i].first)*b[i]);
        }
        if(n==i) break;
        ma=max(ma,b[i]);
    }
    cout<<res<<endl;
    return 0;
}

Submission Info

Judge Result