Submission #398576

#	Time	Username	Problem	Language	Result	Execution time	Memory
398576		nvmdava	Growing Vegetables is Fun 4 (JOI21_ho_t1)	C++17	100 / 100	28 ms	8544 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ff first
#define ss second
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int N = 200005;
const ll MOD = 1000000007;
const ll INF = 0x3f3f3f3f3f3f3f3f;

ll a[N], d[N];
ll l[N], r[N];

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n;
    cin>>n;
    for(int i = 1; i <= n; ++i)
        cin>>a[i];

    for(int i = 1; i < n; ++i)
        d[i] = a[i + 1] - a[i];
    ll t = 0;
    for(int i = 1; i <= n; ++i){
        l[i] += t;
        t += max(0LL, 1 - d[i]);
    }
    t = 0;
    for(int i = n; i >= 1; --i){
        r[i] += t;
        t += max(0LL, d[i - 1] + 1);
    }
    ll ans = 1'000'000'000'000'000'000;
    for(int i = 1; i <= n; ++i)
        ans = min(ans, max(l[i], r[i]));
    cout<<ans;
}

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