Submission #743743

#	Time	Username	Problem	Language	Result	Execution time	Memory
743743		MODDI	Growing Vegetables is Fun 4 (JOI21_ho_t1)	C++14	100 / 100	110 ms	6220 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
typedef long long ll;
typedef pair<long long, long long> pll;
typedef pair<int,int> pii;
typedef vector<long long> vl;
typedef vector<int> vi;
int main(){
	int n;
	cin>>n;
	vi arr(n);
	for(int i = 0; i < n; i++)	cin>>arr[i];
	vector<ll> pref(n), suf(n);
	for(int i = 0; i < n-1; i++){
		pref[i+1] = pref[i] + max(0, arr[i] - arr[i+1] + 1);
	}
	for(int i = n-2; i >= 0; i--){
		suf[i] = suf[i+1] + max(0, arr[i+1] - arr[i] + 1);
	}
	ll ans = 2e15;
	for(int i = 0; i < n; i++){
		ans = min(ans, max(pref[i], suf[i]));
	}
	cout<<ans<<endl;

	return 0;
}

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