제출 #930634

#제출 시각아이디문제언어결과실행 시간메모리
930634mochaGrowing Vegetables is Fun 4 (JOI21_ho_t1)C++14
100 / 100
23 ms9068 KiB
#include <bits/stdc++.h> #define int long long using namespace std; const int mx = 2e5+5; int n; int a[mx], b[mx], c[mx]; int dp[2][mx]; signed main() { cin.tie(0);ios::sync_with_stdio(0); cin >> n; for (int i=0;i<n;i++) { cin >> a[i]; } for (int i=1;i<n;i++) { dp[0][i] = dp[0][i-1] + max(0LL, a[i-1]+1-a[i]); } for (int i=n-2;i>=0;i--) { dp[1][i] = dp[1][i+1] + max(0LL, a[i+1]+1-a[i]); } long long ans = min(dp[0][n-1], dp[1][0]); for (int i=1;i<n-1;i++) { long long m = max(dp[0][i-1], dp[1][i+1]); ans = min(ans, m+max(dp[0][i]-dp[0][i-1],dp[1][i]-dp[1][i+1])); } cout << ans << "\n"; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...