제출 #563007

#제출 시각아이디문제언어결과실행 시간메모리
563007Bill_00Growing Vegetables is Fun 4 (JOI21_ho_t1)C++14
0 / 100
1 ms340 KiB
#include <bits/stdc++.h> #define ff first #define ss second #define N 1000000 typedef long long ll; const ll NIL = 0; using namespace std; ll n, h[N]; pair<ll, ll> dp[2][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 >> h[i]; } for(ll i = 1; i <= n; i++){ if(dp[0][i - 1].ss + h[i - 1] < h[i]){ dp[0][i].ff = dp[0][i - 1].ff; dp[0][i].ss = 0; } else{ dp[0][i].ss = dp[0][i - 1].ss + h[i - 1] + 1 - h[i]; dp[0][i].ff = dp[0][i - 1].ff + (max(NIL, dp[0][i].ss - dp[0][i - 1].ss)); } } for(ll i = n; i >= 1; i--){ if(dp[1][i + 1].ss + h[i + 1] < h[i]){ dp[1][i].ff = dp[1][i + 1].ff; dp[1][i].ss = 0; } else{ dp[1][i].ss = dp[1][i + 1].ss + h[i + 1] + 1 - h[i]; dp[1][i].ff = dp[1][i + 1].ff + (max(NIL, dp[1][i].ss - dp[1][i + 1].ss)); } } ll ans = 1e18; for(ll i = 1; i <= n; i++){ ll height = max(dp[0][i - 1].ss + h[i - 1], dp[1][i + 1].ss + h[i + 1]) + 1; ll many = max(NIL, height - h[i]); ll u = min(dp[0][i - 1].ss, dp[1][i + 1].ss); ll v = max(dp[0][i - 1].ss, dp[1][i + 1].ss); if(many <= v){ ans = min(ans, dp[0][i - 1].ff + dp[1][i + 1].ff - u); } else ans = min(ans, dp[0][i - 1].ff + dp[1][i + 1].ff - u + many - v); } cout << ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...