Submission #623900

#	Time	Username	Problem	Language	Result	Execution time	Memory
623900		Abrar_Al_Samit	Growing Vegetables is Fun 4 (JOI21_ho_t1)	C++17	100 / 100	27 ms	5752 KiB

Main

#include<bits/stdc++.h>
using namespace std;
 
void PlayGround() {
  int n;
  cin>>n;
  int a[n];
  for(int i=0; i<n; ++i) {
    cin>>a[i];
  }
  long long b[n];
  b[0] = a[0];
  for(int i=1; i<n; ++i) {
    b[i] = a[i]-a[i-1];
  }
 
 
  long long ans = LLONG_MAX;

  long long candidate = 0;
  for(int i=1; i<n; ++i) {
    if(b[i]<=0) candidate += abs(b[i])+1;
  }
  ans = min(ans, candidate);
 
  vector<long long>A(n), B(n);
  for(int i=0; i<n; ++i) {
    A[i] = max(0LL, 1-b[i]);
    B[i] = max(0LL, b[i]+1);
    if(i) A[i] += A[i-1];
  }
  for(int i=n-2; i>=0; --i) {
    B[i] += B[i+1];
  }
  for(int i=0; i<n-1; ++i) {
    ans = min(ans, max(A[i],B[i+1]));
  }
  cout<<ans<<'\n';
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  PlayGround();
  return 0;
}

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