제출 #930619

#제출 시각아이디문제언어결과실행 시간메모리
930619mochaGrowing Vegetables is Fun 4 (JOI21_ho_t1)C++14
0 / 100
1 ms6492 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]; } dp[0][0] = 0; b[0] = a[0]; for (int i=1;i<n;i++) { if (a[i] > b[i-1]) { dp[0][i] = dp[0][i-1]; b[i] = a[i]; } else { b[i] = b[i-1]+1; dp[0][i] = dp[0][i-1]; if (b[i]-a[i] > b[i-1]-a[i-1]) { dp[0][i] += b[i]-a[i]-b[i-1]+a[i-1]; } } } dp[1][n-1] = 0;c[n-1] = a[n-1]; for (int i=n-1;i>=0;i--) { if (a[i] > c[i+1]) { dp[1][i] = dp[1][i+1]; c[i] = a[i]; } else { c[i] = c[i+1]+1; dp[1][i] = dp[1][i+1]; if (c[i]-a[i] > c[i+1]-a[i+1]) { dp[1][i] += c[i]-a[i]-c[i+1]+a[i+1]; } } } long long ans = min(dp[0][n-1],dp[1][0]); for (int i=1;i<n-1;i++) { if (b[i]>c[i+1]) { ans = min(ans, dp[0][i]+dp[1][i+1]-min(b[i]-a[i],c[i+1]-a[i+1])); } else { ans = min(ans, dp[0][i-1]+dp[1][i]-min(b[i-1]-a[i-1],c[i]-a[i])); } } cout << ans << "\n"; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...