제출 #1332379

#제출 시각아이디문제언어결과실행 시간메모리
1332379lywoemBitaro the Brave 2 (JOI25_ho_t2)C++20
100 / 100
161 ms31760 KiB
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define l(a, b, i) for (ll i = a; i < b; i++)
#define rl(a, b, i) for (ll i = a; i >= b; i--)
#define vpair vector<pair<ll, ll>>
#define inf LLONG_MAX
#define ninf LLONG_MIN

bool meow(ll X, ll i, vector<ll> &vecA, vector<ll> &vecB, vector<ll> &pre1, vector<ll> &maxneed1, vector<ll> &maxneed2) {
    ll need = max(maxneed1[i], maxneed2[i - 1]) + pre1[i];
    return need <= X;
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    ll N; cin >> N; vector<ll> vecA(N + 1, 0), vecB(N + 1, 0);
    l(1, N + 1, i) cin >> vecA[i];
    l(1, N + 1, i) cin >> vecB[i];

    vector<ll> pre1(N + 1, 0); // cai prefix bthg
    vector<ll> pre2(N + 1, 0); // prefix with wrap-around

// pre1[0] = pre1[1] = 0
// else, pre1[i] = pre1[i - 1] + vecB[i - 1]
    l(2, N + 1, i) pre1[i] = pre1[i - 1] + vecB[i - 1]; 

// pre2[0] = 0
// pre2[1] = pre1[N] + vecB[N] // later need to minus away the pre1[idx we start at]
// else, pre2[i] = pre2[i - 1] + vecB[i - 1]
    pre2[1] = pre1[N] + vecB[N];
    l(2, N + 1, i) pre2[i] = pre2[i - 1] + vecB[i - 1];

    vector<ll> need1(N + 1, 0); // vecA[i] - pre1[i] 
    vector<ll> need2(N + 1, 0); // vecA[i] - pre2[i] (lat nua cung can minus away the pre1[idx we start at])

    l(1, N + 1, i) need1[i] = vecA[i] - pre1[i];

    l(1, N + 1, i) need2[i] = vecA[i] - pre2[i];
    

    vector<ll> maxneed1(N + 1, 0), maxneed2(N + 1, 0);
    maxneed1[N] = need1[N];
    rl(N - 1, 1, i) maxneed1[i] = max(maxneed1[i + 1], need1[i]);

    maxneed2[1] = need2[1];
    l(2, N + 1, i) maxneed2[i] = max(maxneed2[i - 1], need2[i]);

    ll finalans = inf;
    l(1, N + 1, i) {
        ll lo = 0, hi = 1e10, ans = -1;
        while (lo <= hi) {
            ll mid = (lo + hi) / 2;

            if (meow(mid, i, vecA, vecB, pre1, maxneed1, maxneed2)) {
                ans = mid;
                hi = mid - 1;
            }
            else lo = mid + 1;
        }

        if (ans != -1) finalans = min(finalans, ans);
    }

    cout << finalans;
}
#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...