Submission #1325400

#	Time	Username	Problem	Language	Result	Execution time	Memory
1325400		polishprogrammer	Growing Vegetables is Fun 4 (JOI21_ho_t1)	C++20	100 / 100	20 ms	6576 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define fi first
#define se second
#define lld long double
vector<ll> policz(int n, vector<ll> arr) {
    vector<ll> v(n);
    v[0] = 0;
    ll ak = arr[0], z = 0;
    for (int i = 1; i < n; i++) {
        ak = max(ak + 1, arr[i] + v[i-1]);
        v[i] = max(v[i-1], ak - arr[i]);
    }
    return v;
}
int main() {
    ios_base::sync_with_stdio(0);
    cout.tie(0);
    cin.tie(0);
    int n;
    cin >> n;
    vector<ll> arr(n);
    for (int i = 0; i < n; i++) cin >> arr[i];
    vector<ll> l = policz(n, arr);
    reverse(arr.begin(), arr.end());
    vector<ll> p = policz(n, arr);
    reverse(p.begin(), p.end());
    ll wyn = 1e18;
    for (int i = 0; i < n; i++) wyn = min(wyn, max(p[i], l[i]));
    cout << wyn;
}

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