Submission #983945

#	Time	Username	Problem	Language	Result	Execution time	Memory
983945		vjudge1	Growing Vegetables is Fun 4 (JOI21_ho_t1)	C++17	0 / 100	1 ms	348 KiB

Main

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>//i am gay
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define He_he_boy ios_base::sync_with_stdio(0) , cin.tie(0) ,cout.tie(0)
#define ld long double///i like negr a
#define pb push_back
#define pf push_front
#define fi first
#define se second
#define ll long long
#define ull unsigned long long
#define all(a) a.begin(), a.end()
#define open freopen ("herding.in", "r", stdin);
#define close freopen("herding.out", "w", stdout);
using namespace std;
using namespace __gnu_pbds;

const ll mod = 1e9 + 7;
ll mod_2 = 998244353;
typedef tree<long long, null_type, less_equal<long long> /* � ���������� less_equal<ll> */, rb_tree_tag, tree_order_statistics_node_update>pbds;

ll nok(ll n1, ll n2)
{
    return n1 * n2 / __gcd(n1, n2);
}
ll qpow_mod(ll a, ll b, ll md)
{
    ll res = 1;
    a = a % md;
    while (b > 0)
    {
        if (b & 1)
            res = (res * a) % md;
        a = (a * a) % md;
        b >>= 1;
    }
    return res;
}
ll pros(ll n) {
  if (n == 1) {
    return 1;
  }
  for (ll i = 2; i * i <= n; i++) {
    if (n % i == 0) {
      return 0;
    }
  }
  return 1;
}

/// --------------------------------------------------------
void Ali(){
	ll n;
	cin >> n;
	ll a[n + 19] = {}, b[n + 19] = {}, c[n + 19] = {};
	for(ll i = 1;i <= n;i ++){
		cin >> a[i];
		b[i] = a[i];
		c[i] = a[i];
	}
	ll dp[n + 19] = {}, dp2[n + 19] = {}, ans[n + 19] = {};
	for(ll i = 2;i <= n;i ++){
		ans[i] = ans[i - 1];
		if(a[i] <= a[i - 1]){
			dp[i] = a[i - 1] - a[i] + 1;
			a[i] = a[i - 1] + 1;
			if(dp[i - 1] > 0){
				ans[i] += 1;
			}
			else{
				ans[i] += dp[i];
			}
		}
	}
	ll ans2[n + 19] = {};
	for(ll i = n - 1;i >= 1;i --){
		ans2[i] = ans2[i + 1];
		if(b[i + 1] >= b[i]){
			dp2[i] = b[i + 1] - b[i] + 1;
			b[i] = b[i + 1] + 1;
			if(dp2[i + 1] > 0){
				ans2[i] ++;
			}
			else{
				ans2[i] += dp2[i];
			}
		}
	}
	ll mn = 1e18;
	for(ll i = 1;i <= n;i ++){
		ll s = max(a[i - 1], b[i + 1]);
		if(c[i] <= s){
			mn = min(mn, s - c[i] + 1 + max(ans[i - 1], ans2[i + 1]));
		}
		else{
			mn = min(mn, max(ans[i - 1], ans2[i + 1]));
		}
	}
	cout << mn << '\n';
}
/// */* ------------------------------- */*
int main() {
  He_he_boy;
  ll nigga = 1;
 // cin >> nigga;
  while(nigga--){
  	Ali();
  }
  /*
  	Are you sure bro ?
  */
}
/// */* ------------------------------- */*

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