Submission #476883

#	Time	Username	Problem	Language	Result	Execution time	Memory
476883		Rainbowbunny	Growing Vegetables is Fun 4 (JOI21_ho_t1)	C++17	100 / 100	33 ms	8532 KiB

Main

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 2e5 + 5;
const long long INF = 1e18;

int n;
long long A[MAXN];
long long B[MAXN];
long long Pos[MAXN], Neg[MAXN];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    for(int i = 1; i <= n; i++)
    {
        cin >> A[i];
        if(i != 1)
        {
            B[i - 1] = A[i - 1] - A[i];
        }
    }
    for(int i = 1; i <= n; i++)
    {
        Pos[i] = Pos[i - 1];
        if(B[i] >= 0)
        {
            Pos[i] += (B[i] + 1);
        }
    }
    for(int i = n - 1; i >= 1; i--)
    {
        Neg[i] = Neg[i + 1];
        if(B[i] <= 0)
        {
            Neg[i] += (1 - B[i]);
        }
    }
    long long ans = INF;
    for(int i = 1; i <= n; i++)
    {
        ans = min(ans, max(Pos[i - 1], Neg[i]));
    }
    cout << ans << '\n';
}

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