Submission #543682

#TimeUsernameProblemLanguageResultExecution timeMemory
543682Bill_00Growing Vegetables is Fun 4 (JOI21_ho_t1)C++14
0 / 100
1 ms468 KiB
#include <bits/stdc++.h> #define N 200005 #define ff first #define ss second typedef long long ll; const ll MOD = 1000000007; const ll INF = 1000000000; using namespace std; ll n, a[N], l[N], r[N], suml[N], sumr[N], mxl[N], mxr[N]; int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n; for(ll i = 1; i <= n; i++){ cin >> a[i]; } for(ll i = 1; i <= n; i++){ l[i] = max(l[i - 1] + 1, a[i]); if(l[i] - a[i] == 0){ mxl[i] = 0; suml[i] = suml[i - 1] + mxl[i - 1]; } else{ mxl[i] = max(l[i] - a[i], mxl[i - 1]); suml[i] = suml[i - 1]; } } for(ll i = n; i >= 1; i--){ r[i] = max(r[i + 1] + 1, a[i]); if(r[i] - a[i] == 0){ mxr[i] = 0; sumr[i] = sumr[i + 1] + mxr[i + 1]; } else{ mxr[i] = max(r[i] - a[i], mxr[i + 1]); sumr[i] = sumr[i + 1]; } } ll ans = 1e18; for(ll i = 1; i <= n; i++){ ans = min(ans, suml[i] + sumr[i] + max(mxl[i], mxr[i])); } cout << ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...