Submission #936895

#	Time	Username	Problem	Language	Result	Execution time	Memory
936895		emanIaicepsa	Growing Vegetables is Fun 4 (JOI21_ho_t1)	C++14	0 / 100	0 ms	600 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define dbg(...) cerr<<#__VA_ARGS__<<" = ";_do(__VA_ARGS__);
template<typename T> void _do(T x){cerr<<x<<"\n";}
template<typename T,typename ...U> void _do(T x,U ...y){cerr<<x<<", ";_do(y...);}

signed main(){
    ios::sync_with_stdio(0), cin.tie(0);
    int N;
    cin >> N;
    vector<ll> arr(N);
    for (auto &i: arr) cin >> i;

    int lidx = 1, ridx = N - 2;
    while (lidx < N && arr[lidx] > arr[lidx - 1]) lidx++;
    while (ridx >= 0 && arr[ridx] > arr[ridx + 1]) ridx--;

    if (lidx == N || ridx == -1) {
        cout << 0 << '\n';
        return 0;
    }

    ll answer = 0;

    while (lidx < ridx) {
        while (lidx < N && arr[lidx] > arr[lidx - 1]) lidx++;
        while (ridx >= 0 && arr[ridx] > arr[ridx + 1]) ridx--;
        if (lidx > ridx) break;
        ll rdif = arr[ridx + 1] - arr[ridx];
        ll ldif = arr[lidx - 1] - arr[lidx];
        ll add = min(rdif, ldif) + 1;

        answer += add;
        for (int i = lidx; i <= ridx; i++) arr[i] += add;

        // for (int i = 0; i < N; i++) cout << arr[i] << " \n"[i == N - 1];
        // arr[ridx + 1] -= add;
        // arr[lidx - 1] -= add;
    }

    if (arr[lidx] == arr[ridx]) answer++;
    cout << answer << '\n';
}

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