제출 #711559

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
711559		shoryu386	Growing Vegetables is Fun 4 (JOI21_ho_t1)	C++17	0 / 100	1 ms	340 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define MAXN 200007
int n;
int arr[MAXN];

int check(int k){
	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;
}

main(){
	cin >> n;
	for (int x = 0; x < n; x++) cin >> arr[x];
	
	int ans = LONG_LONG_MAX/3;
	
	/*
	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;
	
	while (l < r){
		int m = (l+r)/2;
		
		int cm1 = check(m), cm2 = check(m+1);
		
		ans = min({ans, cm1, cm2});
		
		if (cm1 < cm2){
			r = m;
		}
		else{
			l = m+1;
		}
	}
	
	
	
	
	cout << min({ans, check(0), check(n-1)});
	//theory: can we always set max point as the k? no lol??

}

컴파일 시 표준 에러 (stderr) 메시지

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

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