Submission #712161

#	Time	Username	Problem	Language	Result	Execution time	Memory
712161		shoryu386	Growing Vegetables is Fun 4 (JOI21_ho_t1)	C++17	0 / 100	9 ms	324 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define MAXN 200007
int n;
int arr[MAXN];
int checkCount = 0;
int check(int k){
	checkCount++;
	
	if (checkCount > MAXN/100) return LONG_LONG_MAX/3;
	int left = k, right = k;
	int leftval = arr[k], rightval = arr[k];
	int inc = 0;
	while (left != 0 || right != n-1){
		
		if ((left != 0 && arr[left-1] - leftval < arr[right+1] - rightval) || right == n-1){
			if (arr[left-1] < leftval){
				leftval = arr[left-1]; left--;
			}
			else{
				inc += arr[left-1] - leftval + 1;
				rightval += arr[left-1] - leftval + 1;
				leftval += arr[left-1] - leftval + 1;
				
				leftval -= 1;
				left--;
			}
		}
		else{
			if (arr[right+1] < rightval){
				rightval = arr[right+1]; right++;
			}
			else{
				inc += arr[right+1] - rightval + 1;
				leftval += arr[right+1] - rightval + 1;
				rightval += arr[right+1] - rightval + 1;
				
				
				rightval -= 1;
				right++;
			}
		}
	}
	return inc;
}
int ans = LONG_LONG_MAX/3;
void whatThe(int l, int r){
	if (l >= r) return;
	int m = (l+r)/2;
		
	int cm1 = check(m), cm2 = check(m+1);
		
	ans = min({ans, cm1, cm2});
		
	if (cm1 < cm2){
		r = m-1;
		whatThe(l, r);
	}
	else if (cm1 == cm2){
		whatThe(l, m-1); whatThe(m+1, r);
	}
	else{
		l = m+1;
		whatThe(l, r);
	}
}

main(){
	cin >> n;
	for (int x = 0; x < n; x++) cin >> arr[x];
	
	
	
	/*
	for (int k = 0; k < n; k++){
		//try every point as the breaking point (max value)
		
		ans = min(check(k), ans);
	}
	*/
	
	//derivative bsearch
	
	int l = 0, r = n-2;
	
	whatThe(l, r);
	
	
	
	
	cout << min({ans, check(0), check(n-1)});
	//theory: can we always set max point as the k? no lol??

}

Compilation message (stderr)

Main.cpp:69:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   69 | main(){
      | ^~~~

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