Submission #1081272

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

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long
int leftside[200001], rightside[200001];


int32_t main() {
    int n; cin >> n;
    vector<int> arr(n);
    for (int i=0;i<n;i++) {
        cin >> arr[i];
    }
    

    leftside[0] = 0;
    for (int i=1;i<n;i++) {
        leftside[i] = leftside[i-1] + max(arr[i-1] - arr[i] + 1, (int)0);
    }
    rightside[n-1] = 0;
    for (int i=n-2;i>-1;i--) {
        rightside[i] = rightside[i+1] + max(arr[i+1] - arr[i] + 1, (int)0);
    }


    int ans = INT_MAX, curans;
    if (leftside[n-1] > rightside[0]) {
        ans = rightside[0];
    } else {
        ans = leftside[n-1];
    }
    for (int i=1;i<n-1;i++) {
        curans = leftside[i-1] + rightside[i+1];
        if (arr[i+1] - arr[i] - leftside[i-1] > arr[i-1] - arr[i] - rightside[i+1]) {
            curans += max(arr[i+1] - arr[i] - leftside[i-1] + 1, (int)0);
        } else {
            curans += max(arr[i-1] - arr[i] - rightside[i+1] + 1, (int)0);
        }
        if (curans < ans) {
            ans = curans;
        }
    }
    cout << ans;
}

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