Submission #379150

#	Time	Username	Problem	Language	Result	Execution time	Memory
379150		rocks03	Growing Vegetables is Fun 4 (JOI21_ho_t1)	C++14	100 / 100	31 ms	5004 KiB

Main

//#pragma GCC target("avx2")
//#pragma GCC optimization("O3")
//#pragma GCC optimization("unroll-loops")
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define ff first
#define ss second
#define pb push_back
#define SZ(x) ((int)(x).size())
#define all(x) x.begin(), x.end()
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define Re(i, a, b) for(int i = (a); i >= (b); i--)
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

void solve(){
    int N; cin >> N;
    vector<int> a(N + 2);
    rep(i, 1, N + 1) cin >> a[i];
    vector<ll> l(N + 2, 0), r(N + 2, 0);
    rep(i, 1, N + 1){
        l[i] = l[i - 1] + max((a[i - 1] + 1) - a[i], 0);
    }
    Re(i, N, 1){
        r[i] = r[i + 1] + max((a[i] + 1) - a[i - 1], 0);
    }
    ll ans = LLONG_MAX;
    rep(i, 1, N + 1){
        ans = min(ans, l[i] + max(r[i + 1] - l[i], (ll) 0));
    }
    cout << ans;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
    return 0;
}

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