제출 #1325912

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1325912		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 = 1 , p2 = n;
    int ans = 0;

    while(p1 <= p2){
        // cout << p1 << ' ' << p2 << ' ';

        if (p1 == p2){
            
            int r1 = A[p1-1] - A[p1] + 1 , r2 = A[p2+1] - A[p2] + 1;
            // cout << r1 << ' ' << r2 << ' ' << A[p1] << endl;
            ans += max(0ll , min(r1 , r2));
            break;
        }
        
        if (p1 < p2 && A[p1] > A[p1-1]){
            p1++;
            if (p1 == p2) continue;
            A[p1] += ans;
            // cout << ans << endl;
            continue;
        }

        if (p2 > p1 && A[p2] > A[p2+1]){
            p2--;
            if (p1 == p2) continue;
            A[p2] += ans;
            // cout << ans << endl;
            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;
    } 

    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