Submission #538473

#	Time	Username	Problem	Language	Result	Execution time	Memory
538473		Haruto810198	Growing Vegetables is Fun 4 (JOI21_ho_t1)	C++17	100 / 100	31 ms	11648 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define double long double

#define FOR(i, l, r, d) for(int i=(l); i<=(r); i+=(d))
#define szof(x) ((int)(x).size())

#define vi vector<int>
#define pii pair<int, int>

#define F first
#define S second

#define pb push_back
#define eb emplace_back
#define mkp make_pair

const int INF = INT_MAX;
const int LNF = INF*INF;
const int MOD = 1000000007;

//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")

const int MAX = 200010;

int n;
int arr[MAX];
int dif[MAX];
int cost_i[MAX], cost_d[MAX];
int pref[MAX], suf[MAX];
int res;

signed main(){
	
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	cin>>n;
	FOR(i, 1, n, 1){
		cin>>arr[i];
		dif[i] = arr[i] - arr[i-1];
		cost_i[i] = max((int)0, 1 - dif[i]);
		cost_d[i] = max((int)0, 1 + dif[i]);
	}
	
	FOR(i, 1, n, 1){
		pref[i] = pref[i-1] + cost_i[i];
	}
	for(int i=n; i>=1; i--){
		suf[i] = suf[i+1] + cost_d[i];
	}
	
	res = min(pref[n], suf[1]);
	FOR(i, 1, n-1, 1){
		res = min(res, max(pref[i], suf[i+1]));
	}
	
	cout<<res<<'\n';

	return 0;

}

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