제출 #409145

#제출 시각아이디문제언어결과실행 시간메모리
409145ngpin04Growing Vegetables is Fun 4 (JOI21_ho_t1)C++14
100 / 100
30 ms6140 KiB
#include <bits/stdc++.h> #define fi first #define se second #define mp make_pair using namespace std; const int N = 2e5 + 5; const int oo = 2e9; long long f[N]; long long g[N]; int a[N]; int n; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin >> n; for (int i = 1; i <= n; i++) cin >> a[i]; for (int i = 2; i <= n; i++) f[i] = f[i - 1] + max(0, a[i - 1] - a[i] + 1); for (int i = n - 1; i >= 1; i--) g[i] = g[i + 1] + max(0, a[i + 1] - a[i] + 1); long long ans = 1e18; for (int mid = 1; mid <= n; mid++) { int cost = max(0, max(a[mid - 1], a[mid + 1]) - a[mid] + 1); ans = min(ans, max(f[mid - 1], g[mid + 1]) + cost); } cout << ans; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...