Submission #1346063

#TimeUsernameProblemLanguageResultExecution timeMemory
1346063piolkBitaro the Brave 2 (JOI25_ho_t2)C++20
100 / 100
67 ms20372 KiB
#include <bits/stdc++.h>
using namespace std;

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n;
    cin>>n;

    vector<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];
    vector<long long> P(2*n);
    for (int i=0;i<2*n;i++){
        P[i]=b[i];
        if (i>0) P[i]=P[i-1]+b[i%n];
    }

    deque<pair<int,long long>> dq; //{ind,val}

    for (int i=0;i<n;i++){
        long long pref=(i==0 ? 0 : P[i-1]);
        long long val=a[i]-pref;

        while (!dq.empty() && dq.back().second<val) dq.pop_back();
        dq.push_back({i,val});
    }

    long long ans=max(dq.front().second,0ll);

    for (int i=1;i<n;i++){
        int ii=i+n-1;
        long long val=a[ii%n]-P[ii-1];

        while (!dq.empty() && dq.back().second<val) dq.pop_back();
        dq.push_back({ii,val});

        while (!dq.empty() && dq.front().first<i) dq.pop_front();
        
        long long best=max(P[i-1]+dq.front().second,0ll);

        ans=min(ans,best);

        //cout<<i<<": "<<P[i-1]<<" "<<dq.front().second<<"\n";
    }

    cout<<ans<<"\n";

    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...