oj.uz

Submission #372643

# Submission time Handle Problem Language Result Execution time Memory
372643 2021-03-01T08:06:52 Z SeDunion Growing Vegetables is Fun 4 (JOI21_ho_t1) C++17
0 / 100
 1 ms 364 KB 
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e6 + 66;

ll A[N];

ll p[N], s[N];

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	int n;
	cin >> n;
	for (int i = 1 ; i <= n ; ++ i) cin >> A[i];
	/*for (int i = 1 ; i <= n ; ++ i) {
		vector<int>b(n+1);
		for (int j = 1 ; j <= n ; ++ j) b[j] = A[j];
		ll L = 0, R = 0;
		for (int j = 1 ; j < i ; ++ j) {
			while (b[j + 1] <= b[j]) b[j + 1]++, L++;
		}
		for (int j = n ; j > i ; -- j) {
			while (b[j - 1] <= b[j]) b[j - 1]++, R++;
		}
		ll cur = max(L, R);
		for (int j = 1 ; j <= n ; ++ j) {
			cout << b[j] << " ";
		}
		cout << ": " << cur << "\n";
	}*/
	ll val = 0;
	for (int i = 1 ; i <= n ; ++ i) {
		ll add = max(0ll, val + 1 - A[i]);
		val = max(val, A[i]);
		p[i] = p[i - 1] + add;
	}
	val = 0;
	for (int i = n ; i >= 1 ; -- i) {
		ll add = max(0ll, val + 1 - A[i]);
		val = max(val, A[i]);
		s[i] = s[i + 1] + add;
	}
	ll ans = ll(1e18);
	for (int i = 1 ; i <= n ; ++ i) {
		ans = min(ans, max(p[i], s[i]));
	//	cout << p[i] << ' ';
	}
	/*cout << "\n";
	for (int i = 1 ; i <= n ; ++ i) cout << s[i] << " ";
	cout << "\n";
	*/cout << ans;
}

Subtask #1
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Incorrect 1 ms 364 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Incorrect 1 ms 364 KB Output isn't correct
6 Halted 0 ms 0 KB -