Submission #529499

#	Time	Username	Problem	Language	Result	Execution time	Memory
529499		syl123456	Growing Vegetables is Fun 4 (JOI21_ho_t1)	C++17	100 / 100	31 ms	5956 KiB

Main

#include <bits/stdc++.h>
#define all(i) (i).begin(), (i).end()
using namespace std;
#define debug(args) cout << '[' << #args << "] is [", DEBUG(false, args...), cout << endl
template<typename T>
void DEBUG(bool _sp, T i) {
    if (_sp)
        cout << ' ';
    cout << i;
}
template<typename T, typename ...U>
void DEBUG(bool _sp, T i, U ...j) {
    if (_sp)
        cout << ' ';
    cout << i;
    DEBUG(j...);
}
typedef long long ll;
typedef pair<int, int> pi;
typedef double dd;

const int inf = 0x3f3f3f3f, lg = 20;
const ll mod = 1e9 + 7, INF = 0x3f3f3f3f3f3f3f3f;

signed main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int n;
    cin >> n;
    int a[n];
    for (int &i : a)
        cin >> i;
    vector<ll> d;
    d.push_back(inf);
    for (int i = 1; i < n; ++i)
        d.push_back(a[i] - a[i - 1]);
    d.push_back(-inf);
    vector<ll> pre(n + 1), suf(n + 1);
    pre[0] = suf[n] = 0;
    for (int i = 1; i <= n; ++i)
        pre[i] = pre[i - 1] + max(0ll, 1 - d[i]);
    for (int i = n - 1; ~i; --i)
        suf[i] = suf[i + 1] + max(0ll, d[i] + 1);
    ll ans = INF;
    for (int i = 0; i < n; ++i)
        ans = min(ans, max(pre[i], suf[i + 1]));
    cout << ans;
}

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