Submission #1230606

#	Time	Username	Problem	Language	Result	Execution time	Memory
1230606		biank	Growing Vegetables is Fun 4 (JOI21_ho_t1)	C++20	100 / 100	13 ms	5068 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define forsn(i, s, n) for (int i = int(s); i < int(n); i++)
#define forn(i, n) forsn(i, 0, n)
#define dforsn(i, s, n) for (int i = int(n) - 1; i >= int(s); i--)
#define dforn(i, n) dforsn(i, 0, n)

#define sz(x) int(x.size())
#define all(x) begin(x), end(x)

using ll = long long;
using ld = long double;
using vi = vector<int>;
using vb = vector<bool>;
using vll = vector<ll>;
using ii = pair<int, int>;
using iii = tuple<int, int, int>;

#define fst first
#define snd second

#define pb push_back
#define eb emplace_back

const ll INF = 1e18;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    int n;
    cin >> n;
    vi a(n);
    forn(i, n) cin >> a[i];
    vi d(n - 1);
    forn(i, n - 1) d[i] = a[i + 1] - a[i];
    vll pref(n), suff(n);
    pref[0] = 0LL;
    forn(i, n - 1) {
        pref[i + 1] = pref[i] + max(0, 1 - d[i]);
    }
    suff[n  - 1] = 0LL;
    dforn(i, n - 1) {
        suff[i] = suff[i + 1] + max(0, d[i] + 1);
    }
    ll ret = INF;
    forn(i, n) ret = min(ret, max(pref[i], suff[i]));
    cout << ret << '\n';
    
    return 0;
}

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