제출 #1010489

#제출 시각아이디문제언어결과실행 시간메모리
1010489AlmontherGrowing Vegetables is Fun 4 (JOI21_ho_t1)C++98
0 / 100
1 ms348 KiB
#include <bits/stdc++.h> #define suiii ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); #define ll long long #define co cout<< //#pragma GCC optimize("O3,Ofast,unroll-loops") //#pragma GCC target("avx2,sse3,sse4,avx") using namespace std; //stuff ll n; ll arr[1000001]; ll pref[100001]; ll suff[1000001]; ll val[1000001]; ll val1[1000001]; ll mn=1e18; ll cnt=0; void solve(){ cin>>n; for(int i=1;i<=n;i++) cin>>arr[i]; for(int i=2;i<=n;i++){ ll last=arr[i-1]+val[i-1]; ll diff=(last+1)-arr[i]; val[i]=max(diff,0ll); } for(int i=1;i<=n;i++){ pref[i]=pref[i-1]; if(val[i]>val[i-1]) pref[i]+=val[i]-val[i-1]; } for(int i=n-1;i>=1;i--){ ll last=arr[i+1]+val1[i+1]; ll diff=(last+1)-arr[i]; val1[i]=max(diff,0ll); } for(int i=n;i>=1;i--){ suff[i]=suff[i+1]; if(val1[i]>val1[i+1]) suff[i]+=val1[i]-val1[i+1]; } // for(int i=1;i<=n;i++){ // co pref[i-1]<<' '<<suff[i+1]<<'\n'; // if(i==5) co "here "<<pref[i]<<' '<<suff[i+1]<<'\n'; // } // return; for(int i=1;i<=n;i++){ ll ans=max(pref[i],suff[i]); if(pref[i]==suff[i]) ans++; mn=min(mn,ans); } co mn; } int main() { suiii int tt=1; // cin>>tt; while(tt--){ solve(); } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...