Submission #415843

#	Time	Username	Problem	Language	Result	Execution time	Memory
415843		meatrow	Growing Vegetables is Fun 4 (JOI21_ho_t1)	C++17	100 / 100	49 ms	3136 KiB

Main

// #pragma GCC target ("avx2")
// #pragma GCC optimization ("O3")
#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using ld = long double;

const int MOD = 1e9 + 7;

ll binpow(ll a, ll p, int mod = MOD) {
    ll res = 1;
    while (p) {
        if (p & 1) {
            (res *= a) %= mod;
        }
        p >>= 1;
        (a *= a) %= mod;
    }
    return res;
}

ll gcd(ll a, ll b) {
    return b == 0 ? a : gcd(b, a % b);
}

void solve() {
    int n;
    cin >> n;
    vector<int> b;
    int last = 0;
    ll left = 0, right = 0;
    for (int i = 0; i < n; i++) {
        int a;
        cin >> a;
        if (i) b.push_back(a - last);
        last = a;

        if (i && b.back() >= 0) right += b.back() + 1;
    }

    ll ans = right;
    for (int i = 0; i + 1 < n; i++) {
        if (b[i] >= 0) right -= b[i] + 1;
        if (b[i] <= 0) left -= b[i] - 1;
        ans = min(ans, max(left, right));
    }

    cout << ans << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T = 1;
    // cin >> T;
    for (int tc = 1; tc <= T; tc++) {
        // cout << "Case #" << tc << ": ";
        solve();
    }
    return 0;
}

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