제출 #736389

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
736389		LCJLY	Growing Vegetables is Fun 4 (JOI21_ho_t1)	C++14	100 / 100	27 ms	8532 KiB

Main

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

#define int long long 
typedef pair<int,int>pii;

int32_t main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	int n;
	cin >> n;
	
	int arr[n+5];
	int diff[n+5];
	memset(diff,0,sizeof(diff));
	
	for(int x=1;x<=n;x++){
		cin >> arr[x];
		if(x>1){
			diff[x]=arr[x]-arr[x-1];
		}
	}
	
	//precompute
	int left[n+5];
	int right[n+5];
	memset(left,0,sizeof(left));
	memset(right,0,sizeof(right));
	
	//positive gradient
	for(int x=2;x<=n;x++){
		left[x]=left[x-1]+max(0LL,1-diff[x]);
	}
	
	//negative gradient 
	for(int x=n;x>=2;x--){
		right[x]=right[x+1]+max(0LL,1+diff[x]);
	}
	
	//combine
	int best=LONG_LONG_MAX;
	for(int x=1;x<=n;x++){
		int hold=max(left[x],right[x+1]);
		best=min(best,hold);
	}
	cout << best;
}

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