Submission #543691

#	Time	Username	Problem	Language	Result	Execution time	Memory
543691		Bill_00	Growing Vegetables is Fun 4 (JOI21_ho_t1)	C++14	0 / 100	1 ms	468 KiB

Main

#include <bits/stdc++.h>

#define N 200005
#define ff first
#define ss second
typedef long long ll;
const ll MOD = 1000000007;
const ll INF = 1000000000;
using namespace std;

ll n, a[N], l[N], r[N], suml[N], sumr[N], mxl[N], mxr[N], befl[N], befr[N];
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    cin >> n;
    for(ll i = 1; i <= n; i++){
        cin >> a[i];
    }
    ll L = 0, R = n + 1;
    for(ll i = 1; i <= n; i++){
        l[i] = max(l[i - 1] + 1, a[i]);
        if(l[i] - a[i] == 0){
            mxl[i] = 0;
            suml[i] = suml[i - 1] + mxl[i - 1];
            L = i;
        }
        else{
            befl[i] = L;
            mxl[i] = max(l[i] - a[i], mxl[i - 1]);
            suml[i] = suml[i - 1];
        }
    }
    for(ll i = n; i >= 1; i--){
        r[i] = max(r[i + 1] + 1, a[i]);
        if(r[i] - a[i] == 0){
            mxr[i] = 0;
            sumr[i] = sumr[i + 1] + mxr[i + 1];
            R = i;
        }
        else{
            befr[i] = R;
            mxr[i] = max(r[i] - a[i], mxr[i + 1]);
            sumr[i] = sumr[i + 1];
        }
    }
    ll ans = 1e18;
    for(ll i = 1; i <= n; i++){
        ans = min(ans, suml[befl[i]] + sumr[befr[i]] + max(max(mxl[i - 1], mxr[i + 1]), max(l[i] - a[i], r[i] - a[i])));
    }
    cout << ans;


}

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