Submission #623808

#	Time	Username	Problem	Language	Result	Execution time	Memory
623808		Abrar_Al_Samit	Growing Vegetables is Fun 4 (JOI21_ho_t1)	C++17	0 / 100	0 ms	320 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];
  }
  if(n==2) {
    cout<<"0\n";
    return;
  }
  long long b[n-1];
  for(int i=1; i<n; ++i) {
    b[i-1] = a[i]-a[i-1];
  }


  long long ans = LLONG_MAX;
  int prev = a[0];
  long long cur = 0;
  for(int i=1; i<n; ++i) {
    int add = max(0, prev+1-a[i]);
    cur += add;
    prev = a[i]+add;
  }
  ans = cur;
  cur = 0;
  prev = a[n-1];
  for(int i=n-2; i>-1; --i) {
    int add = max(0, prev+1-a[i]);
    cur += add;
    prev = a[i]+add;
  }
  ans = min(ans, cur);

  vector<long long>A(n-1), B(n-1);
  for(int i=0; i<n-1; ++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-3; i>=0; --i) {
    B[i] += B[i+1];
  }
  for(int i=0; i<n-2; ++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: 0 / 40
• Subtask 2: 0 / 60