제출 #1369884

#제출 시각아이디문제언어결과실행 시간메모리
1369884makskusBitaro the Brave 2 (JOI25_ho_t2)C++20
31 / 100
43 ms16348 KiB
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <deque>
#include <cmath>
#include <climits>
#include <cstring>
#include <iomanip>
#include <numeric>
#include <functional>
#include <bitset>
#include <unordered_map>
#include <unordered_set>
#include <chrono>
#include <random>

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
#define rep(a,b) for(int a = 0;a<b;a++)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(),a.end()
const int inf = 1e9;
const ll infl = 1e18;

const ll ize = 500007; 
ll tr[ize*2];

void add(ll p, ll v)
{
    p += ize;
    tr[p] = v;
    p /= 2;
    while(p > 0)
    {
        tr[p] = max(tr[p*2], tr[p*2+1]);
        p /= 2;
    }
}

ll check(ll l, ll r)
{
    l += ize;
    r += ize;
    ll ans = tr[l];
    if(l != r) ans = max(ans, tr[r]);
    while(l/2 != r/2)
    {
        if(l%2==0) ans = max(ans, tr[l+1]);
        if(r%2==1) ans = max(ans, tr[r-1]);
        l /= 2; r /= 2;
    }
    return ans;
}

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

    rep(i, ize*2) tr[i] = -infl; 

    int n;
    cin >> n;

    vector<int> a(2*n);
    vector<int> b(2*n);

    rep(i, n){
        cin >> a[i];
        a[i+n] = a[i];
    }
    rep(i, n){
        cin >> b[i];
        b[i+n] = b[i];
    }

    ll p = 0; 
    rep(i, 2*n){
        add(i, (ll)a[i] - p);
        p += b[i];
    }

    ll w = infl;
    p = 0;

    rep(i, n){
        ll x = check(i, i + n - 1) + p;
        w = min(w, x);
        p += b[i];
    }

    cout << max(0LL, w) << "\n";
    
    return 0;
}
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…