Submission #891346

#	Time	Username	Problem	Language	Result	Execution time	Memory
891346		EJIC_B_KEDAX	Growing Vegetables is Fun 4 (JOI21_ho_t1)	C++17	100 / 100	41 ms	3956 KiB

Main

#ifdef LOCAL
    //#define _GLIBCXX_DEBUG
#endif
#include <bits/stdc++.h>
#include <random>

#ifndef LOCAL
    //#pragma GCC optimize("O3")
    //#pragma GCC optimize("Ofast")
    //#pragma GCC optimize("unroll-loops")
    #pragma GCC target("avx,avx2,bmi,bmi2,popcnt,lzcnt")
#endif
using namespace std;
using ll = long long;
using ld = long double;
#define x first
#define y second
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()

mt19937_64 mt(418);

void solve();
void init();

int32_t main() {
#ifndef LOCAL
    cin.tie(nullptr)->sync_with_stdio(false);
#endif
    // srand(time(0));
    init();
    cout << fixed << setprecision(20);
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
}

void init() {}

#define int ll

const int N = 200200;
int a[N];

void solve() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    int x = 0, y = n - 1;
    ll ans = 0;
    while (y > x && x < n - 1) {
        while (y > x && x < n - 1 && a[x] < a[x + 1]) {
            x++;
        }
        while (y > x && a[y] < a[y - 1]) {
            y--;
        }
        if (y > x && x < n - 1) {
            int c = min(a[x] - a[x + 1], a[y] - a[y - 1]) + 1, x1 = x, y1 = y;
            ans += c;
            if (a[x] - a[x + 1] < c) {
                x++;
            }
            if (a[y] - a[y - 1] < c) {
                y--;
            }
            a[x1] -= c;
            a[y1] -= c;
        }
    }
    cout << ans << '\n';
}

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