Submission #426725

#	Time	Username	Problem	Language	Result	Execution time	Memory
426725		tengiz05	Growing Vegetables is Fun 4 (JOI21_ho_t1)	C++17	0 / 100	1 ms	204 KiB

Main

#include <bits/stdc++.h>
using i64 = long long;
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int n;
    std::cin >> n;
    std::vector<i64> a(n);
    for (int i = 0; i < n; i++) {
        std::cin >> a[i];
    }
    i64 ans = 0;
    auto update = [&](int l, int r, i64 val) {
        for (; l <= r; l++) {
            a[l] += val;
        }
    };
    for (int l = 1, r = n - 1; l <= r; ) {
        while (l < n && a[l] > a[l - 1]) l++;
        while (r - 1 >= 0 && a[r - 1] > a[r]) r--;
        if (l == r) {
            ans++;
            break;
        }
        if (l > r) break;
        i64 val = std::min(a[l - 1] + 1 - a[l], a[r] + 1 - a[r + 1]);
        update(l, r - 1, val);
        ans += val;
        // std::cout << l << " " << r << "\n";
        // for (int i = 0; i < n; i++) {
        //     std::cout << a[i] << " ";
        // } std::cout << "\n";
    }
    std::cout << ans << "\n";
    return 0;
}

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