Submission #711535

#	Time	Username	Problem	Language	Result	Execution time	Memory
711535		shoryu386	Growing Vegetables is Fun 4 (JOI21_ho_t1)	C++17	0 / 100	16 ms	344 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 = INT_MAX;
	for (int k = 0; k < n; k++){
		//try every point as the breaking point (max value)
		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);
		
		
		//cout << k << '\n';
		//for (int x = 0; x < n; x++) cout << arr[x] + increase[x] << ' ';
		//cout << '\n';
		
		
		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 << 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: 0 / 40
• Subtask 2: 0 / 60