Submission #942209

#	Time	Username	Problem	Language	Result	Execution time	Memory
942209		ErJ	Growing Vegetables is Fun 4 (JOI21_ho_t1)	C++17	100 / 100	17 ms	2136 KiB

Main

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define vi vector<ll>
#define vvi vector<vector<ll>>
#define vs vector<string>
#define vc vector<char>
#define vb vector<bool>
#define vp vector<pair<ll, ll>>
#define pp pair<ll, ll>
#define qi queue<ll>
#define qp queue<pp>
#define pqi priority_queue<ll>
#define pqp priority_queue<pp>
#define mi map<ll, ll>
#define mpi map<pp, ll>
#define mip map<ll, pp>
#define mpp map<pp, pp>
#define mb map<ll, bool>
#define si set<ll>
#define sp set<pp>
#define mod 1000000007
#define rep(a, b) for(int a = 0; a < (b); a++)
#define rep2(a, b) for(int a = 1; a < (b); a++)
#define inf 1000000000000000000

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int n;
	cin >> n;
	vi A(n);
	rep(i, n) {
		cin >> A[i];
	}
	int l = 0; int r = n - 1;
	ll ans = 0;
	while (l < r) {
		
		while (l + 1 < n && A[l] < A[l + 1]) {
			l++;
		}
		while (r-1 >= 0 && A[r] < A[r - 1]) {
			r--;
		}
		if (l + 1 == r && A[l] == A[r]) {
			ans++;
			break;
		}
		if (!(l < r)) {
			break;
		}
		int xl = A[l] - A[l + 1] + 1;
		int xr = A[r] - A[r - 1] + 1;
		int xmin = min(xl, xr);
		A[l] -= xmin;
		A[r] -= xmin;
		ans += xmin;
	}
	cout << ans << endl;
}

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