제출 #1324218

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1324218		sh_qaxxorov_571	Growing Vegetables is Fun 4 (JOI21_ho_t1)	C++20	100 / 100	19 ms	6600 KiB

Main

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

/**
 * JOI 2021 Final Round - Biba-herbs
 * Vaqt murakkabligi: O(N)
 */

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

    int N;
    cin >> N;
    vector<long long> A(N + 1);
    for (int i = 1; i <= N; i++) {
        cin >> A[i];
    }

    if (N == 1) {
        cout << 0 << endl;
        return 0;
    }

    vector<long long> diff(N);
    for (int i = 1; i < N; i++) {
        diff[i] = A[i + 1] - A[i];
    }

    // pref[i] - 1-dan i-gacha o'suvchi qilish uchun kerakli amallar
    vector<long long> pref(N + 1, 0);
    for (int i = 1; i < N; i++) {
        long long cost = 0;
        if (diff[i] <= 0) {
            cost = abs(diff[i]) + 1;
        }
        pref[i + 1] = pref[i] + cost;
    }

    // suff[i] - i-dan N-gacha kamayuvchi qilish uchun kerakli amallar
    vector<long long> suff(N + 1, 0);
    for (int i = N - 1; i >= 1; i--) {
        long long cost = 0;
        if (diff[i] >= 0) {
            cost = diff[i] + 1;
        }
        suff[i] = suff[i + 1] + cost;
    }

    long long min_ops = -1;
    for (int k = 1; k <= N; k++) {
        // k cho'qqi bo'lganda kerakli sug'orishlar soni
        long long current_ops = max(pref[k], suff[k]);
        if (min_ops == -1 || current_ops < min_ops) {
            min_ops = current_ops;
        }
    }

    cout << min_ops << endl;

    return 0;
}

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