Submission #503726

#	Time	Username	Problem	Language	Result	Execution time	Memory
503726		couplefire	Growing Vegetables is Fun 4 (JOI21_ho_t1)	C++17	100 / 100	31 ms	6716 KiB

Main

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

#define ll long long

const int N = 200005;

int n; ll arr[N];
ll ldp[N], rdp[N];

int main(){
    // freopen("a.in", "r", stdin);
    cin.tie(0)->sync_with_stdio(0);
    cin >> n;
    for(int i = 0; i<n; ++i)
        cin >> arr[i];
    for(int i = 1; i<n; ++i)
        ldp[i] = ldp[i-1]+max(0ll, arr[i-1]-arr[i]+1);
    for(int i = n-1; i>=0; --i)
        rdp[i] = rdp[i+1]+max(0ll, arr[i+1]-arr[i]+1);
    ll ans = 1e18;
    for(int i = 0; i<n; ++i)
        ans = min(ans, max(ldp[i], rdp[i]));
    cout << ans << '\n';
}

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