Submission #1326232

#	Time	Username	Problem	Language	Result	Execution time	Memory
1326232		hssaan_arif	Growing Vegetables is Fun 4 (JOI21_ho_t1)	C++20	100 / 100	16 ms	1996 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+1 < p2){
        // cout << p1 << ' ' << p2 << ' ' << ans << endl;

        // for (int i=1 ; i<=n ; i++){
        //     cout << A[i] << ' ';
        // }
        // cout << endl;

        if (p1 + 2 == p2){
            int r1 = A[p1] - A[p1+1] + 1 , r2 = A[p2] - A[p2-1] + 1;
            A[p1+1] += min(max(0ll,r1),max(0ll,r2));
            ans += min(max(0ll,r1),max(0ll,r2));

            if (A[p1+1] == A[p1] || A[p1+1] == A[p2]){
                ans++;
            }
            break;
        }
        
        
        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;
        }
    } 

    // cout << p1 << ' ' << p2 << endl;

    

    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: 40 / 40
• Subtask 2: 60 / 60