제출 #1355139

#제출 시각아이디문제언어결과실행 시간메모리
1355139d4n13lBitaro the Brave 2 (JOI25_ho_t2)C++20
100 / 100
230 ms19988 KiB
#include <bits/stdc++.h>
#define int long long

using namespace std;

void solve() {
    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];
    }
    for (int i = 0; i < n; i++) {
        a.push_back(a[i]);
        b.push_back(b[i]);
    }
    int l = 0, r = 1e18;
    while (l<r) {
        int mid = (l+r)/2;
        int cop = mid;
        bool pos = true;
        for (int i = 2*n-1; i>=n; i--) {
            cop-=b[i];
            if (cop<a[i]) {
                pos = false;
                break;
            }
        }
        if (pos) {
            r=mid;
        } else {
            l=mid+1;
        }
    }
    //cout << l << endl;
    int cop = l;
    for (int i = 2*n-1; i>=n; i--) {
        cop-=b[i];
    }
    int hardest = n;
    vector <int> suf(n+1);
    for (int i = n-1; i >= 0; i--) {
        suf[i]=suf[i+1]+b[i];
    }
    int small = 1e18;
    for (int i = n-1; i >= 0; i--) {
        int one = cop-suf[i];
        int two = a[hardest]-(suf[i]-suf[hardest]);
        if (a[i]>two) {
            two = a[i];
            hardest=i;
        }
        int ansi = max(one, two);
        small = min(ansi, small);
    }
    cout << small << endl;
    return;
}

signed main() {
    int t = 1;
    while (t--) {
        solve();
    }
}
#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...