제출 #448263

#제출 시각아이디문제언어결과실행 시간메모리
448263JovanBGrowing Vegetables is Fun 4 (JOI21_ho_t1)C++17
100 / 100
33 ms10080 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; using ld = long double; const int MAXN = 200000; ll a[MAXN+5]; ll pref[MAXN+5]; ll suf[MAXN+5]; ll hpref[MAXN+5]; ll hsuf[MAXN+5]; const ll INF = 1000000000000000000LL; int main(){ ios_base::sync_with_stdio(false), cin.tie(0); cout.precision(10); cout << fixed; int n; cin >> n; for(int i=1; i<=n; i++){ cin >> a[i]; } for(int i=1; i<=n; i++){ hpref[i] = max(hpref[i-1] + 1, a[i] + pref[i-1]); pref[i] = pref[i-1] + max(0LL, hpref[i] - (a[i] + pref[i-1])); } for(int i=n; i>=1; i--){ hsuf[i] = max(hsuf[i+1] + 1, a[i] + suf[i+1]); suf[i] = suf[i+1] + max(0LL, hsuf[i] - (a[i] + suf[i+1])); } ll res = INF; for(int i=1; i<=n; i++){ res = min(res, max(pref[i-1], max(suf[i+1], max(hpref[i-1], hsuf[i+1]) + 1 - a[i]))); } cout << res << "\n"; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...