Submission #1326229

#	Time	Username	Problem	Language	Result	Execution time	Memory
1326229		hssaan_arif	Growing Vegetables is Fun 4 (JOI21_ho_t1)	C++20	0 / 100	1 ms	332 KiB

Main

// #include <bits/stdc++.h>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <map>
#include <unordered_map>
#include <vector>
#include <iomanip>
#include <string>
#include <queue>
#include <set>
#include <deque>
using namespace std;

#define endl "\n"
#define pb push_back
#define int long long
#define fi first
#define se second

const int N = 3e5 + 5, M = 1e9 + 7, LG = 20;

int n , A[N];

void solve(){
    cin >> n;

    A[0] = -1e18;
    A[n+1] = -1e18;

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

    int p1 = 0 , p2 = n+1;
    int ans = 0;

    while(p1+2 <= p2){
        // cout << p1 << ' ' << p2 << ' ' << ans << endl;

        // for (int i=1 ; i<=n ; i++){
        //     cout << A[i] << ' ';
        // }
        
        
        if (A[p1+1] > A[p1]){
            p1++;
            if (p1+2 == p2) continue;
            A[p1+1] += ans;
            continue;
        }

        if (A[p2-1] > A[p2]){
            p2--;
            if (p1+2 == p2) continue;
            A[p2-1] += ans;
            continue;
        }

        
        int r1 = A[p1] - A[p1+1] + 1 , r2 = A[p2] - A[p2-1] + 1;
        // cout << r1 << ' ' << r2 << endl;

        if (r1 <= r2){
            ans += r1;
            A[p1+1] += r1;
            A[p2-1] += r1;
        }else{
            ans += r2;
            A[p2-1] += r2;
            A[p1+1] += r2;
        }
    } 

    if (A[p1] == A[p2]){
        ans++;
    }

    cout << ans << endl;
}

signed main(){
    // freopen("" , "r" , stdin);
    // freopen("" , "w" , stdout);
    // cout << setprecision(30);
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int ts = 1;
    // cin >> ts;
    while(ts--){
        solve();
    }
}

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