Submission #503473

#	Time	Username	Problem	Language	Result	Execution time	Memory
503473		InternetPerson10	Growing Vegetables is Fun 4 (JOI21_ho_t1)	C++17	100 / 100	34 ms	11724 KiB

Main

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

ll plant_vegetables(vector<ll> nums) {
    int n = nums.size();
    vector<ll> le(n), ri(n), rel(n), rer(n);
    rel[0] = nums[0];
    rer[n-1] = nums[n-1];
    for(int i = 1; i < n; i++) {
        le[i] = le[i-1] + max(0LL, nums[i-1] - nums[i] + 1);
        rel[i] = max(nums[i], nums[i-1]+1);
    }
    for(int i = n-2; i >= 0; i--) {
        ri[i] = ri[i+1] + max(0LL, nums[i+1] - nums[i] + 1);
        rer[i] = max(nums[i], nums[i+1]+1);
    }
    ll ans = 1234567891234567890;
    for(int i = 0; i < n; i++) {
        ans = min(ans, max(le[i], ri[i]));
    }
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    vector<ll> nums(n);
    for(int i = 0; i < n; i++) cin >> nums[i];
    cout << plant_vegetables(nums) << '\n';
}

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