Submission #1149946

#	Time	Username	Problem	Language	Result	Execution time	Memory
1149946		henriess	Growing Vegetables is Fun 4 (JOI21_ho_t1)	C++20	0 / 100	0 ms	324 KiB

Main

#include <bits/stdc++.h>
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;
    vector<long long> A(N), L(N), R(N);

    // Read the initial heights A
    for(int i = 0; i < N; i++){
        cin >> A[i];
    }

    // 1) Build L: minimal strictly increasing (left -> right) with L[i] >= A[i].
    //    i.e. L[i] = max(A[i], L[i-1] + 1)
    L[0] = A[0];
    for(int i = 1; i < N; i++){
        L[i] = max(A[i], L[i-1] + 1);
    }

    // 2) Build R: minimal strictly *decreasing* in left-to-right sense,
    //    which we can do by going right->left and enforcing R[i] >= R[i+1] + 1.
    R[N-1] = A[N-1];
    for(int i = N - 2; i >= 0; i--){
        R[i] = max(A[i], R[i+1] + 1);
    }

    // 3) Final B: B[i] = min(L[i], R[i])
    vector<long long> B(N);
    for(int i = 0; i < N; i++){
        B[i] = min(L[i], R[i]);
    }

    // 4) Compute the minimum # of water-intervals using the "difference array" trick
    long long ans = 0LL;
    long long prevX = 0LL; // x_0 = 0
    for(int i = 0; i < N; i++){
        long long x = B[i] - A[i];  // how many total increments needed at i
        ans += max(0LL, x - prevX); // add positive jump
        prevX = x;
    }

    // Output the result
    cout << ans << "\n";
    return 0;
}

• Subtask 1: 0 / 40
• Subtask 2: 0 / 60