제출 #443575

#제출 시각아이디문제언어결과실행 시간메모리
443575MilosMilutinovicGrowing Vegetables is Fun 4 (JOI21_ho_t1)C++14
100 / 100
46 ms9288 KiB
#include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(0); int n; cin >> n; vector<int> a(n); for (int i = 0; i < n; i++) { cin >> a[i]; } const long long inf = 1e18; long long ans = inf; vector<long long> pref(n); vector<long long> suff(n); vector<long long> x(n), y(n); for (int i = 0; i < n; i++) { x[i] = a[i]; y[i] = a[i]; } for (int i = 0; i < n; i++) { if (i > 0) { pref[i] = pref[i - 1]; x[i] = max(a[i], a[i - 1] + 1); } pref[i] += x[i] - a[i]; } for (int i = n - 1; i >= 0; i--) { if (i < n - 1) { suff[i] = suff[i + 1]; y[i] = max(a[i], a[i + 1] + 1); } suff[i] += y[i] - a[i]; } if (n == 1) { cout << 0 << '\n'; return 0; } for (int i = 0; i < n; i++) { long long cur = inf; if (i > 0) { cur = min(cur, pref[i - 1]); } if (i < n - 1) { cur = min(cur, suff[i + 1]); } ans = min(ans, max(pref[i], suff[i])); } cout << ans << '\n'; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...