Submission #421257

#	Time	Username	Problem	Language	Result	Execution time	Memory
421257		rqi	Growing Vegetables is Fun 4 (JOI21_ho_t1)	C++14	100 / 100	105 ms	6956 KiB

Main

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

typedef long long ll;

void ckmin(ll& a, ll b){
	a = min(a, b);
}

const ll INF = 1e18;

const int mx = 200005;
int N;
ll A[mx];
ll ans1[mx];
ll ans2[mx];

int main(){
	cin >> N;
	for(int i = 1; i <= N; i++){
		cin >> A[i];
	}


	 for(int i = 2; i <= N; i++){
	 	ans1[i] = ans1[i-1]+max(ll(0), 1-(A[i]-A[i-1]));
	 }

	 for(int i = N; i >= 2; i--){
	 	ans2[i] = ans2[i+1]+max(ll(0), 1+(A[i]-A[i-1]));
	 }


	 ll ans = INF;
	 for(int i = 1; i <= N; i++){
	 	//cout << i << " " << ans1[i] << " " << ans2[i] << "\n";
	 	ckmin(ans, max(ans1[i], ans2[i+1]));
	 }

	 cout << ans << "\n";
}

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