제출 #1092272

#제출 시각아이디문제언어결과실행 시간메모리
1092272PagodePaivaGrowing Vegetables is Fun 4 (JOI21_ho_t1)C++17
40 / 100
54 ms13136 KiB
#include<bits/stdc++.h> #define int long long using namespace std; const int N = 200010; int addpref[N], addsuf[N]; int nump[N], nums[N]; int v[N]; int32_t main(){ int n; cin >> n; for(int i = 1;i <= n;i++) cin >> v[i]; nump[1] = v[1]; for(int i = 2;i <= n;i++){ nump[i] = max(nump[i-1]+1, v[i]); } nums[n] = v[n]; for(int i = n-1;i >= 1;i--){ nums[i] = max(nums[i+1]+1, v[i]); } for(int i = 1;i <= n;i++){ addpref[i] = nump[i] - v[i]; addsuf[i] = nums[i] - v[i]; } int pref[N], suf[N]; pref[1] = 0; int ant = 0; for(int i = 2;i <= n;i++){ pref[i] = pref[i-1]; if(ant < addpref[i]) pref[i] += addpref[i] - ant; ant = addpref[i]; } ant = 0; for(int i = n-1;i > 0;i--){ suf[i] = suf[i+1]; if(ant < addsuf[i]) suf[i] += addsuf[i] - ant; ant = addsuf[i]; } int res = 1e18; for(int i = 1;i <= n;i++){ res = min(res, (addpref[i] > addsuf[i] ? max(pref[i], suf[i+1]) : max(pref[i-1], suf[i]))); } cout << res << '\n'; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...