Submission #711546

#	Time	Username	Problem	Language	Result	Execution time	Memory
711546		shoryu386	Growing Vegetables is Fun 4 (JOI21_ho_t1)	C++17	40 / 100	1081 ms	3740 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long
main(){
	int n; cin >> n;
	int arr[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)
		
		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++;
				}
			}
		}
		//cout << inc << ' ';
		ans = min(inc, ans);
		
		/*
		int increase[n]; memset(increase, 0, sizeof(increase));
		int runningmax = -1;
		for (int x = 0; x <= k; x++){
			if (arr[x] <= runningmax+1) increase[x] = runningmax - arr[x] + 1;
			
			if (arr[x]+increase[x] > runningmax) runningmax = arr[x]+increase[x];
		}
		
		int initkInc = increase[k];
		
		runningmax = -1;
		for (int x = n-1; x >= k; x--){
			if (arr[x] <= runningmax+1) increase[x] = runningmax - arr[x] + 1;
			
			if (arr[x]+increase[x] > runningmax) runningmax = arr[x]+increase[x];
		}
		
		increase[k] = max(increase[k], initkInc);
		
		
		
		
		if (k != 0) increase[k] = max(increase[k-1], increase[k]);
		if (k != n-1) increase[k] = max(increase[k+1], increase[k]);
		int runsum = 0;
		int curHeight = 0;
		for (int x = 0; x < n; x++){
			if (curHeight > increase[x]){
				curHeight = increase[x];
			}
			else if (curHeight < increase[x]){
				runsum += increase[x] - curHeight, curHeight = increase[x];
			}
		}
		
		cout << k << '\n';
		for (int x = 0; x < n; x++) cout << arr[x] + increase[x] << ' ';
		cout << '\n';
		cout << runsum << "\n\n";
		
		ans = min(ans, runsum);
		* */
		
	}
	cout << ans;
	//theory: can we always set max point as the k? no lol??

}

Compilation message (stderr)

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

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