Submission #983846

#	Time	Username	Problem	Language	Result	Execution time	Memory
983846		vjudge1	Growing Vegetables is Fun 4 (JOI21_ho_t1)	C++17	100 / 100	25 ms	6912 KiB

Main

#define Magic ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define en '\n'
#define tsts int t; cin >> t; while(t--)
#define all(a) a.begin() , a.end()
#define open freopen ("leftout.in", "r", stdin);
#define close freopen("leftout.out", "w", stdout);
#define pb push_back
#define fi first
#define se secondя
typedef long long ll;
typedef long double ld;
const ll INF = 1e15 + 7;
const int N = 3000008;
using namespace std;

typedef __gnu_pbds::tree<int, __gnu_pbds::null_type, less<int>, __gnu_pbds::rb_tree_tag, __gnu_pbds::tree_order_statistics_node_update> ordered_set;

ll lcm(ll a, ll b)
{
    return (a * b) / __gcd(a, b);
}
 
ll bp (ll a, ll n) {
	if (n == 0)
		return 1;
	if (n % 2 == 1)
		return bp (a, n-1) * a;
	else {
		ll b = bp (a, n/2);
		return b * b;
	}
}
ll bp_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 in() {ll x; cin >> x; return x;};

// -------------------------------------------------------------------------------------------------------------------------------------------------------------

void solve(){
	ll n = in();
	ll a[n+18];
	for(ll i = 1; i <= n; ++i) a[i] = in();
	ll dp1[n+18];
	ll dp2[n+18];
	dp1[1] = 0;
	dp2[n+1] = 0;
	dp1[0] = 1;
	ll mx = a[1];
	ll sum = 0;
	for(ll i = 2; i <= n; ++i){
		dp1[i] = dp1[i-1];
		if(a[i] + dp1[i] <= mx){
			dp1[i] += mx - (a[i] + dp1[i]) + 1;
			mx++;
		}else{
			mx = a[i] + dp1[i];
		}
	}
	dp2[n] = 0;
	mx = a[n];
	for(ll i = n - 1; i >= 1; --i){
		dp2[i] = dp2[i+1];
		if(a[i] + dp2[i] <= mx){
			dp2[i] += mx - (a[i] + dp2[i]) + 1;
			mx++;
		}else{
			mx = a[i] + dp2[i];
		}
	}
	ll ans = 1e15;
	for(ll i = 0; i <= n; ++i){
		ll ch = max(dp1[i], dp2[i+1]);
		if(a[i] + dp1[i] == a[i+1] + dp2[i+1]){
			if(dp1[i] == dp2[i + 1]) ch++;
		}
		ans = min(ans, ch);
	}
	cout << ans;
}

signed main() {
	Magic
//	open freopen ("swap.in", "r", stdin); close freopen("swap.out", "w", stdout);
//	tsts{
		solve();
		cout << en;
//	}    
}

Compilation message (stderr)

Main.cpp: In function 'void solve()':
Main.cpp:64:5: warning: unused variable 'sum' [-Wunused-variable]
   64 |  ll sum = 0;
      |     ^~~

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