Submission #1092275

#	Time	Username	Problem	Language	Result	Execution time	Memory
1092275		PagodePaiva	Growing Vegetables is Fun 4 (JOI21_ho_t1)	C++17	100 / 100	97 ms	13148 KiB

Main

#include<bits/stdc++.h>
#define int long long

using namespace std;

const int N = 200010;

int addpref[N], addsuf[N];
int nump[N], nums[N];
int v[N];

int32_t main(){
    int n;
    cin >> n;
    for(int i = 1;i <= n;i++)
        cin >> v[i];
    nump[1] = v[1];
    for(int i = 2;i <= n;i++){
        nump[i] = max(nump[i-1]+1, v[i]);
    }
    nums[n] = v[n];
    for(int i = n-1;i >= 1;i--){
        nums[i] = max(nums[i+1]+1, v[i]);
    }
    for(int i = 1;i <= n;i++){
        addpref[i] = nump[i] - v[i];
        addsuf[i] = nums[i] - v[i];
    }  
    int pref[N], suf[N];
    pref[1] = 0;
    int ant = 0;
    for(int i = 2;i <= n;i++){
        pref[i] = pref[i-1];
        if(ant < addpref[i]) pref[i] += addpref[i] - ant;
        ant = addpref[i];
    }
    ant = 0;
    suf[n] = 0;
    for(int i = n-1;i > 0;i--){
        suf[i] = suf[i+1];
        if(ant < addsuf[i]) suf[i] += addsuf[i] - ant;
        ant = addsuf[i];
    }
    int res = 1e18;
    for(int i = 1;i <= n;i++){
        if(addpref[i] == addsuf[i]) res = min(res, min(max(pref[i], suf[i+1]), max(pref[i-1], suf[i])));
        res = min(res, (addpref[i] > addsuf[i] ? max(pref[i], suf[i+1]) : max(pref[i-1], suf[i])));
    }
    cout << res << '\n';
}

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