제출 #1330235

#제출 시각아이디문제언어결과실행 시간메모리
1330235bradley0927Bitaro the Brave 2 (JOI25_ho_t2)C++20
72 / 100
334 ms14056 KiB
#include <iostream>
#include <vector>
#include <climits>
using namespace std;
int main() {
    int n;
    cin >> n;
    vector<int> a(n), b(n);//str req, gain

    for (int i = 0; i < n; i++) cin >> a[i];
    for (int i = 0; i < n; i++) cin >> b[i];
    vector<int> gain(n), gain_rev(n), str(n), str_rev(n), dp(n);
    //gain = str gained from going i to end, gain_rev = str gained from first i
    //str = str req to go from i to end, str_rev = str req to go from 1 to i, dp[i] = str_rev[i] - gain[i]
    gain[n-1] = b[n-1];
    for (int i = n-2; i >= 0; i--) gain[i] = gain[i+1] + b[i];

    gain_rev[0] = b[0];
    for (int i = 1; i < n; i++) gain_rev[i] = gain_rev[i-1] + b[i];

    str[n-1] = a[n-1];
    for (int i = n-2; i >= 0; i--) str[i] = max(0,max(a[i], str[i+1] - b[i]));

    str_rev[0] = a[0];
    for (int i = 1; i < n; i++) str_rev[i] = max(0,max(str_rev[i-1], a[i] - gain_rev[i-1]));

    for (int i = 0; i < n; i++) dp[i] = max(0,str_rev[i] - gain[i]);

    int m = INT_MAX;
    for (int i = 0; i < n; i++) {
        m = min(m, max(str[i], dp[i]));
    }
    cout << m << endl;
}
#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...