제출 #426624

#제출 시각아이디문제언어결과실행 시간메모리
426624milleniumEeeeGrowing Vegetables is Fun 4 (JOI21_ho_t1)C++17
100 / 100
36 ms6956 KiB
#include <bits/stdc++.h> #define fr first #define sc second #define pii pair<int, int> #define pb push_back #define szof(s) (int)s.size() #define all(s) s.begin(), s.end() #define fastInp ios_base::sync_with_stdio(0); cin.tie(0); #define int long long template<class T>void chmax(T &a, T b){if (a < b)a = b;} template<class T>void chmin(T &a, T b){if (b < a)a = b;} using namespace std; const int MAXN = (int)2e5 + 5; const int INF = 1e18; int a[MAXN]; int suf[MAXN], pref[MAXN]; signed main() { fastInp; int n; cin >> n; for (int i = 1; i <= n; i++) { cin >> a[i]; } for (int i = n - 1; i >= 1; i--) { suf[i] = suf[i + 1] + max(0ll, a[i + 1] - a[i] + 1); } int ans = suf[1]; for (int i = 2; i < n; i++){ pref[i] = pref[i - 1] + max(0ll, a[i - 1] - a[i] + 1); ans = min(ans, max(pref[i], suf[i])); } pref[n] = pref[n - 1] + max(a[n - 1] - a[n] + 1, 0ll); ans = min(ans, pref[n]); cout << ans << endl; } /* 8 12 2 34 85 4 91 29 85 */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...