Submission #1006978

#	Time	Username	Problem	Language	Result	Execution time	Memory
1006978		faqinyeager	Growing Vegetables is Fun 4 (JOI21_ho_t1)	C++17	100 / 100	57 ms	7252 KiB

Main

#include <bits/stdc++.h>
#define ff first
#define ss second
using namespace std;
using ll = long long;
 
int n;
vector<ll> a, pref, suff;
 
int main(){
    cin >> n;
    
    a.resize(n);
    pref.resize(n, 0);
    suff.resize(n, 0);
    
    for(int i = 0; i < n; i++) cin >> a[i];
    
    for(int i = 1; i < n; i++) if(a[i - 1] >= a[i]) pref[i] = a[i - 1] - a[i] + 1;
    for(int i = n - 2; i >= 0; i--) if(a[i] <= a[i + 1]) suff[i] = a[i + 1] - a[i] + 1;
    
    for(int i = 1; i < n; i++) pref[i] += pref[i - 1];
    for(int i = n - 2; i >= 0; i--) suff[i] += suff[i + 1];
    
    if(pref[n - 1] == 0 || suff[0] == 0){
        cout << 0; return 0;
    }
    
    ll ans = 1e14;
    
    for(int i = 0; i < n; i++){
        ans = min(ans, max(pref[i], suff[i]));
    }
    
    cout << ans;
}

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