Submission #850864

#TimeUsernameProblemLanguageResultExecution timeMemory
850864dungzGrowing Vegetables is Fun 4 (JOI21_ho_t1)C++17
100 / 100
22 ms10240 KiB
//#pragma GCC optimize ("O2") #include<bits/stdc++.h> using namespace std; #define ll long long #define fi first #define se second #define endl '\n' #define task "task" #define task "task" #define prll pair<ll,ll> #define pb push_back #define ld long double const ll MIN=-1e18,MAX=1e18,MOD=1e9+7,nmax=200005; ll a[nmax],h1[nmax],h2[nmax],cost1[nmax],cost2[nmax]; int main(){ //freopen (task".inp", "r", stdin); //freopen (task".out", "w", stdout); ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); int n; cin>>n; for(int i=1;i<=n;i++) { cin>>a[i]; } h1[1]=a[1]; for(int i=2;i<=n;i++) { if(a[i]<=a[i-1]) { cost1[i]=cost1[i-1]+a[i-1]-a[i]+1; h1[i]=h1[i-1]+1; } else { cost1[i]=cost1[i-1]; h1[i]=max(h1[i-1]+1,a[i]); } } h2[n]=a[n]; for(int i=n-1;i>=1;i--) { if(a[i]<=a[i+1]) { cost2[i]=cost2[i+1]+a[i+1]-a[i]+1; h2[i]=h2[i+1]+1; } else { cost2[i]=cost2[i+1]; h2[i]=max(h2[i+1]+1,a[i]); } } // for(int i=1;i<=n;i++) // { // cout<<cost1[i]<<" "; // } // cout<<endl; // for(int i=1;i<=n;i++) // { // cout<<h1[i]<<" "; // } // cout<<endl; // for(int i=1;i<=n;i++) // { // cout<<cost2[i]<<" "; // } // cout<<endl; // for(int i=1;i<=n;i++) // { // cout<<h2[i]<<" "; // } // cout<<endl; // cout<<cost1[3]<<" "<<cost2[4]; ll ans=min(cost2[1],cost1[n]); for(int i=2;i<n;i++) { ans=min(ans,max(cost1[i],cost2[i+1])+(h1[i]==h2[i+1])); } cout<<ans; } /* 8 12 2 34 85 4 91 29 85 */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...