Submission #1325914

#	Time	Username	Problem	Language	Result	Execution time	Memory
1325914		hssaan_arif	Growing Vegetables is Fun 4 (JOI21_ho_t1)	C++20	0 / 100	0 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 = 1 , p2 = n;
    int ans = 0;

    while(p1 <= p2){

        if (p1 == p2){
            int r1 = A[p1-1] - A[p1] + 1 , r2 = A[p2+1] - A[p2] + 1;
            if (r1 > r2) swap(r1 , r2);
            
            if (r1 > 0){
                ans += r1;
            }else if (r2 > 0){
                ans += r2;
            }
            break;
        }
        
        if (p1 < p2 && A[p1] > A[p1-1]){
            p1++;
            if (p1 == p2) continue;
            A[p1] += ans;
            continue;
        }

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

        
        int r1 = A[p1-1] - A[p1] + 1 , r2 = A[p2+1] - A[p2] + 1;

        if (r1 <= r2){
            ans += r1;
            A[p1] += r1;
            A[p2] += r1;
            p1++;
            if (p1 == p2) continue;
            A[p1] += ans;
        }else{
            ans += r2;
            A[p2] += r2;
            A[p1] += r2;
            p2--;
            if (p1 == p2) continue;
            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