제출 #838661

#제출 시각아이디문제언어결과실행 시간메모리
838661LeVanThucGrowing Vegetables is Fun 4 (JOI21_ho_t1)C++17
0 / 100
1 ms340 KiB
#include<bits/stdc++.h> using namespace std; #define ll long long #define fi first #define se second #define p(x,y) pair<ll,ll>(x,y) #define BIT(i,x) ((x>>i)&1) #define MASK(x) (1<<x) #define ld long double #define __builtin_popcount __builtin_popcountll #define pll pair<ll,ll> template<class T1,class T2> bool maximize(T1 &x,const T2 &y) { if(x<y) { x=y; return 1; } return 0; } template<class T1,class T2> bool minimize(T1 &x,const T2 &y) { if(x>y) { x=y; return 1; } return 0; } void online() { std::ios_base::sync_with_stdio(0); cin.tie(0); #ifdef thuc freopen("input.INP","r",stdin); freopen("output.OUT","w",stdout); #endif } const ll N=2e5+10,M=998244353; ll a[N],n,l[N],r[N],f[N]; int main() { online(); cin>>n; ll ans=1e18; for(int i=1;i<=n;i++) { cin>>a[i]; if(i==1||a[i]<=a[i-1]) l[i]=i; else l[i]=l[i-1]; f[i]=f[i-1]+max(0ll,a[i-1]+1-a[i]); } for(int i=n;i>=1;i--) { if(i==n||a[i]<=a[i+1]) r[i]=i; else r[i]=r[i+1]; minimize(ans,max(0ll,max(a[l[i]-1]+1-a[l[i]],a[r[i]+1]+1-a[r[i]]))+f[l[i]-1]+f[r[i]+1]); f[i]=f[i+1]+max(0ll,a[i+1]+1-a[i]); } cout<<ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...