Submission #602181

#	Time	Username	Problem	Language	Result	Execution time	Memory
602181		HamletPetrosyan	Growing Vegetables is Fun 4 (JOI21_ho_t1)	C++17	100 / 100	34 ms	7036 KiB

Main

/// #if (code == true)

#include <bits/stdc++.h>
using namespace std;

#define pll pair<long long, long long>
#define len(a) ((int)((a).size()))
#define all(a) a.begin(), a.end()
#define add push_back
#define mkp make_pair
#define ll long long
#define fr first
#define sc second

const long long INF = 1000000000ll * 1000000003ll;
const long long MOD = 1000000007ll;
const int N = 2e5 + 5;

ll n, a[N], pref[N], suf[N];

void solve(){
	cin >> n;
	for(int i = 0; i < n; i++){
		cin >> a[i];
		if(i > 0) pref[i] = pref[i - 1] + max(0ll, a[i - 1] + 1 - a[i]);
	}
	for(int i = n - 2; i >= 0; i--){
		suf[i] = suf[i + 1] + max(0ll, a[i + 1] + 1 - a[i]);
	}
	ll ans = min(suf[0], pref[n - 1]);
	for(int i = 1; i < n - 1; i++){
		ans = min(ans, max(suf[i], pref[i]));
//		if(ans == 11){
//			cout << i << " " << pref[i] << " " << suf[i] << endl;
//		}
	}
	cout << ans << "\n";
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int _ = 1;
	// cout << fixed;
	// cout.precision(15);

	// cin >> _ ;
	while(_--) solve();
	return 0;
}

/// #else
/// #include <bits/stdc++.h> using namespace std; int main() { cout << "Hello World!"; }
/// #endif

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