Submission #718038

#	Time	Username	Problem	Language	Result	Execution time	Memory
718038		niter	Growing Vegetables is Fun 4 (JOI21_ho_t1)	C++14	0 / 100	1071 ms	212 KiB

Main

/// 2021 A
#include <bits/stdc++.h>
#define pii pair<int,int>
using namespace std;

int arr[200005];

//void db(){
//    cout << "\n";
//}
//template<class T, class ...U>
//void db(T a, U ...b){
//    cout << a << " "; db(b...);
//}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n, i;
    cin >> n;

    for (i=1; i<=n; i++)
        cin >> arr[i];

    if(n == 2){
        if(arr[1] == arr[2]) cout << "1\n";
        else cout << "0\n";
        return 0;
    }

    for(int i = n; i >= 1; i--){
        arr[i] = arr[i-1];
    }
    arr[1] = 0;
    arr[n+1] = 0;

    int l = 1, r = n+1;
    int cnt = 0;

    while (l + 2 <= r) {
        //db(l, r);
        if(arr[l] >= arr[l+1]){
            cnt++;
            arr[l+1]++;
            arr[r-1]++;
        }
        else{
            while(l + 2 <= r && arr[l] < arr[l+1]){
                l++;
                arr[l+1] += cnt;
            }
            if(l + 1 == r) break;
        }
        if(arr[r] >= arr[r-1]){
            cnt++;
            arr[l-1]++;
            arr[r-1]++;
        }
        else{
            while(l + 2 <= r && arr[r-1] < arr[r]){
                r--;
                arr[r-1] += cnt;
            }
            if(l + 1 == r) break;
        }
    }
    cout << cnt << endl;

    return 0;
}

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