제출 #1279506

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1279506		hanguyendanghuy	Growing Vegetables is Fun 4 (JOI21_ho_t1)	C++20	100 / 100	16 ms	1952 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define fi first
#define se second
constexpr ll MAXN=5e5+5,MAXV=1e5,MOD=1e9+7,INF=1e18;
ll n,m,i,j,p,k,ans,dem,st,en,a[MAXN],dp1[MAXN],dp2[MAXN],b[MAXN],last1[MAXN],last2[MAXN];
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
//    freopen("test.inp","r",stdin);
//    freopen("test.out","w",stdout);
    cin>>n;
    for(i=1;i<=n;i++) cin>>a[i];
    ll l=1,r=n,ans=0,need1=0,needr=0;
    while(l<=r){
        if(a[l]+need1>a[l-1]){
            a[l]+=need1;
            l++;
        }
        else if(a[r]+needr>a[r+1]){
            a[r]+=needr;
            r--;
        }
        else{
            ll nl=a[l-1]-(a[l]+need1)+1,nr=a[r+1]-(a[r]+needr)+1;
            if(nl<=nr){
                need1+=nl;
                needr+=nl;
                a[l]+=need1;
                l++;
            }
            else{
                need1+=nr;
                needr+=nr;
                a[r]+=needr;
                r--;
            }
        }
    }
    if(a[r]==a[l]) need1++;
    cout<<need1;
}

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