제출 #1080771

#제출 시각아이디문제언어결과실행 시간메모리
1080771IcelastGrowing Vegetables is Fun 4 (JOI21_ho_t1)C++17
100 / 100
24 ms10228 KiB
#include <iostream> #include <bits/stdc++.h> #define ll long long using namespace std; const ll maxn = 2*1e5+5, INF = 4e18+9; void solve(){ int n; cin >> n; vector<ll> a(n+2, 0), b, c; for(int i = 1; i <= n; i++){ cin >> a[i]; } vector<ll> pf(n+1, 0), sf(n+2, 0); b = a; for(int i = 1; i <= n; i++){ pf[i] = pf[i-1]; b[i] += pf[i-1]; if(b[i] <= b[i-1]){ pf[i] += b[i-1]-b[i]+1; b[i] = b[i-1]+1; } } c = a; for(int i = n; i >= 1; i--){ sf[i] = sf[i+1]; c[i] += sf[i+1]; if(c[i] <= c[i+1]){ sf[i] += c[i+1]-c[i]+1; c[i] = c[i+1]+1; } } ll ans = INF; for(int i = 1; i <= n+1; i++){ ll res = max(pf[i-1], sf[i]); if(b[i-1] == c[i]){ res++; } ans = min(ans, res); } //cout << pf[1] << " " << sf[2] << "\n"; cout << ans; } int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); solve(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...