Submission #563007

#	Time	Username	Problem	Language	Result	Execution time	Memory
563007		Bill_00	Growing Vegetables is Fun 4 (JOI21_ho_t1)	C++14	0 / 100	1 ms	340 KiB

Main

#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;
}

• Subtask 1: 0 / 40
• Subtask 2: 0 / 60