Submission #412988

#	Time	Username	Problem	Language	Result	Execution time	Memory
412988		FerThugGato12500	Growing Vegetables is Fun 4 (JOI21_ho_t1)	C++11	0 / 100	1 ms	460 KiB

Main

#include <bits/stdc++.h>
using namespace std;
const int lmt  = 200005;    
const long long MOD = 1000000007;

#define f first 
#define S second
#define ll long long
#define ld long double
#define ull unsigned long long
#define forn(i, n) for(int i = 0; i < int(n); i++)
#define for1(i, n) for(int i = 1; i < int(n); i++)
#define forv(i,a,n) for(int i = int(a); i < int(n); i++)
#define rof(i, n) for(int i = int(n); i >= 0; i--)
#define rofv(i,a,n) for(int i = int(n); i >= int(a); i--)
#define pb push_back
#define ins insert
#define pai pair<int, int>
#define pal pair<long long, long long>
#define vi vector<int>
#define vl vector<long long>
#define vld vector<long double>
/*
struct wer{
    int a, b;
};
bool operator < (const wer &a, const wer &b){
    return a.a < b.a;
}*/
ll dp[2][lmt];
ll ok[lmt];
ll OK[lmt];
ll D_[lmt];
ll D[lmt];
ll p[lmt];
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int n; cin>>n;
    for(int i = 0; i < n; i++){
        cin>>p[i];
    }
    if(n==2){
        cout<<(p[0]==p[1] ? 1 : 0);
        return 0;
    }
    int l = 1, r = n-2;
    while(l<r){
        while(l < r && p[l]>p[l-1]){
            l++;
        }
        while(r>l && p[r]>p[r+1]){
            r--;
        }
        if(r<=l || p[r]>p[r+1] || p[l]>p[l-1]){
            break;
        }
        ll x = p[r+1] - p[r], y = p[l-1] - p[l];
        if(x>y){
            dp[1][r] = x-y;
        }else{
            dp[0][l] = y-x;
        }
        l++; r--;
    }
    for(int i = 1; i < n; i++){
        dp[0][i] += dp[0][i-1];
    }
    for(int i = n-2; i >= 0; i--){
        dp[1][i] += dp[1][i+1];
    }
    int L = p[0];
    for(int i = 1; i < n-1; i++){
        if(p[i]>p[i-1]){
            if(p[i]<=L){
                L++;
            }else{
                L = p[i];
            }
            D[i] = D[i-1];
        }else{
            L++;
            D[i] = D[i-1] + (p[i-1] - p[i]) + 1;
        }
        ok[i]=L;
    }
    ll d = D[n-2];
    if(ok[n-2]==p[n-1]){
        d++;
    }
    L = p[n-1];
    for(int i = n-2; i > 0; i--){
        if(p[i]>p[i+1]){
            if(p[i]<=L){
                L++;
            }else{
                L = p[i];
            }
            D_[i] = D_[i+1];
        }else{
            L++;
            D_[i] = D_[i+1] + (p[i+1] - p[i]) + 1;
        }
        OK[i]=L;
    }
    if(OK[1]==p[0]){
        d = min(d, D_[1] + 1);
    }else{
        d = min(d, D_[1]);
    }
    for(int i = 1; i < n-2; i++){
        if(p[i]==p[i+1]){
            d = min(d, max(D[i] + dp[1][i+1], D_[i+1] + dp[0][i]) + 1);
        }else{
            d = min(d, max(D[i] + dp[1][i+1], D_[i+1] + dp[0][i]));
        }
    }
    cout<<d;
    return 0;

}

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