Submission #1341628

#TimeUsernameProblemLanguageResultExecution timeMemory
1341628username77Bitaro the Brave 2 (JOI25_ho_t2)C++20
100 / 100
94 ms23888 KiB
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    // Optimize standard I/O operations for competitive programming
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    if (!(cin >> n)) return 0;

    // Use long long to prevent overflow, as constraints can push sums to ~5 * 10^14
    vector<long long> a(n), b(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    for (int i = 0; i < n; i++) cin >> b[i];

    // 1. Calculate Prefix Sums of Strength Gains
    // P[i] stores the total strength gained AFTER defeating monsters 0 to i
    vector<long long> P(n);
    P[0] = b[0];
    for (int i = 1; i < n; i++) {
        P[i] = P[i-1] + b[i];
    }

    // Helper lambda to get strength gained BEFORE fighting monster i
    auto get_G = [&](int i) {
        return (i == 0) ? 0LL : P[i-1];
    };

    // 2. Calculate Baseline Deficits (Assuming we start at index 0)
    // D[i] = Required strength for monster i minus the strength we naturally built up to reach it
    vector<long long> D(n);
    for (int i = 0; i < n; i++) {
        D[i] = a[i] - get_G(i);
    }

    // 3. Precompute Prefix and Suffix Maximums of the Deficits
    vector<long long> pref_max(n), suff_max(n);
    
    pref_max[0] = D[0];
    for (int i = 1; i < n; i++) {
        pref_max[i] = max(pref_max[i-1], D[i]);
    }

    suff_max[n-1] = D[n-1];
    for (int i = n - 2; i >= 0; i--) {
        suff_max[i] = max(suff_max[i+1], D[i]);
    }

    // Total strength gained from defeating ALL monsters
    long long P_total = P[n-1]; 
    
    // Initialize minimum required initial strength to infinity
    long long min_initial_strength = 2e18; 

    // 4. Evaluate Every Starting Position in O(1) Time per position
    for (int j = 0; j < n; j++) {
        long long G_j = get_G(j);
        
        // Phase 1: Fighting monsters from j to the end of the line (n-1)
        long long req_phase1 = suff_max[j] + G_j;
        
        // Phase 2: Wrapping around and fighting monsters from 0 to j-1
        long long req_phase2 = -2e18; // Default to very small if j == 0 (no Phase 2)
        if (j > 0) {
            req_phase2 = pref_max[j-1] + G_j - P_total;
        }
        
        // The minimum strength needed if starting at j is the max requirement of both phases (or 0)
        long long current_req = max({0LL, req_phase1, req_phase2});
        
        // Update global minimum
        min_initial_strength = min(min_initial_strength, current_req);
    }

    cout << min_initial_strength << "\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...