Submission #1010482

#TimeUsernameProblemLanguageResultExecution timeMemory
1010482AlmontherGrowing 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++){ pref[i]=pref[i-1]; val[i]=0; ll last=arr[i-1]+val[i-1]; if(arr[i]<last+1){ ll diff=(last+1)-arr[i]; val[i]=diff; } } 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--){ suff[i]=suff[i+1]; val1[i]=0; ll last=arr[i+1]+val1[i+1]; if(arr[i]<last+1){ ll diff=(last+1)-arr[i]; val1[i]=diff; } } 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++){ if(pref[i-1]>suff[i+1]){ ll mynum=arr[i]+suff[i]; ll num1=arr[i-1]+pref[i-1]+1; mn=min(mn,pref[i-1]+max(0ll,num1-mynum)); } else if(pref[i-1]==suff[i+1]){ ll mynum=arr[i]+suff[i]; ll num1=arr[i-1]+pref[i-1]+1; mn=min(mn,pref[i-1]+max(0ll,num1-mynum)); mynum=arr[i]+pref[i]; num1=arr[i+1]+suff[i+1]+1; mn=min(mn,suff[i+1]+max(0ll,num1-mynum)); } else{ ll mynum=arr[i]+pref[i]; ll num1=arr[i+1]+suff[i+1]+1; mn=min(mn,suff[i+1]+max(0ll,num1-mynum)); } } 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...