1012C - Hills - CodeForces Solution

// हर हर महादेव
// Author: Praveen Kumar
// Problem: C. Hills
// Contest: Codeforces - Codeforces Round 500 (Div. 1) [based on EJOI]
// URL: https://codeforces.com/problemset/problem/1012/C
// Memory Limit: 512 MB
// Time Limit: 1000 ms
 
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define int long long int
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordred_set; 
//member functions :(-- use less_equal to make it multiset)
//1. order_of_key(k) : number of elements strictly lesser than k
//2. find_by_order(k) : k-th element in the set
#define ff first
#define se second
#define mp make_pair
#define pb push_back
#define print(x) cout<<x<<"\n"
#define yes cout<<"Yes\n"
#define no  cout<<"No\n"
#define nl  cout<<"\n";
#define setbits(x) __builtin_popcountll(x)
#define print2d(dp,n,m) for(int i=0;i<n;i++){for(int j=0;j<m;j++)cout<<dp[i][j]<<" ";cout<<"\n";}
#define minv(a) (*min_element((a).begin(), (a).end()))
#define maxv(a) (*max_element((a).begin(), (a).end()))
#define mina(a,n) (*min_element(a, a+n))
#define maxa(a,n) (*max_element(a, a+n))
#define IO	cin.sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define lb(a, x) (lower_bound((a).begin(), (a).end(), (x))-(a).begin())
#define ub(a, x) (upper_bound((a).begin(), (a).end(), (x))-(a).begin())
#define all(x) (x).begin(), (x).end()
#define rall(x) x.rbegin(), x.rend()
#define printv(v) for(auto e : v) cout<<e<<" "
#define pushv(v, n) for(int i=0;i<n;i++) cin>>v[i]
#define bsearch(v, x) binary_search(v.begin(), v.end(), x)
#define sz(x) ((int)(x).size())
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<double, double> pdd;
typedef vector<int> vi;
typedef map<int, int> mi;
typedef unordered_map<int, int> umi;
typedef priority_queue<int> mxpq;
typedef priority_queue <int, vector<int>, greater<int>> mnpq; 
const int mod = 1e9+7;
const int inf = (int)1e9;
const double eps = 1e-9;
const int mxm = 1e5 + 5;
 
//-------------------DSU-----------------
vector<int>parent;
void make_set(int n){
    parent.resize(n+5); 
    for(int i=0;i<n+5;i++){
     parent[i]=i;
 }
}
int find(int x){
       if( parent[x] == x) {
            return x;
        }
       return parent[x]=find(parent[x]);
    }
 
bool union_set(int x,int y){
        int p=find(x);
        int q=find(y);
        if(p==q){
            return true;
        }
        parent[p]=q;
        return false;
    }
//-----------------digit sum of no---------------
    int digitsum(int n)
    {
        int sum = 0;
        while (n != 0) {
            sum = sum + n % 10;
            n = n / 10;
        }
        return sum;
    }
//---------------LCM---------------
int lcm(int a, int b)
{
    int g=__gcd(a, b);
    return a/g*b;
}
//---------prime checker-----------------
void prime(bool isPrime[]){
for(int i=0;i<=1000000;i++){
	isPrime[i]=1;
}
isPrime[1]=0;
isPrime[0]=0;
for(int i=2;i*i<=1000000;i++){
	if(isPrime[i]==1){
		for(int j=i*i;j<=1000000;j+=i){
			isPrime[j]=0;
		}
	}
  }
}
//---------smallest prime factor-------------
void _spf(int spf[]){
	for(int i=0;i<=1e6;i++){
        spf[i] = i;
    }
    for(int i=2;i*i<=1e6;i++){
        if(spf[i]==i){
            for(int j=i*i;j<=1e6;j+=i){
                if(spf[j]==j){
                    spf[j]=i;
                }
            }
        }
    }
 
}
//-------------no ofg distinct gcd of array in (mx)log(mx)------------
vector<int>  distinctGCDs(vector<int> &arr, int N){
    
     vi distinct;int M = -1, ans = 0; umi Mp;
    for (int i = 0; i < N; i++) {
        M = max(M, arr[i]);
        Mp[arr[i]] = 1;
    }
    for (int i = 1; i <= M; i++) {// variable to check current GCD
        int currGcd = 0;// iterate over all multiples of i
        for (int j = i; j <= M; j += i) {// If j is present in A
            if (Mp[j]) {// calculate gcd of all encountered | multiples of i
                currGcd = __gcd(currGcd, j);// current GCD is possible
                if (currGcd == i) {
                	distinct.pb(currGcd); ans++;break;
                } } }} // return answer
    return distinct;
}
//------------factorial------------------------
void fact(int fac[])
{
    fac[0]=1;
    for(int i=1;i<=1e6;i++){
        fac[i] = fac[i-1]*i; // (a*b)%m = ((a%m)*(b%m))%m
        fac[i]%=mod;
    }
}
//---------binary exponantiation----------------
int binExp(int x,int n)
{
    int res=1;
    while(n){
        if(n%2==1){
            res*=x;
            res%=mod;
        }
        n/=2;
        x*=x;
        x%=mod;
    }
    return res;
}
//--------------ncr-------------------------------
int ncr(int n,int r,int fac[])
{
    int temp1 = fac[n];
    int temp2 = fac[n-r]*fac[r];
    temp2%=mod;
    int temp3 = binExp(temp2,mod-2); // temp3 is the modulo inverse
    temp1*=temp3;
    temp1%=mod;
    return temp1;
}
//------------prime factorization------------------
vector<long long> div(long long n) {
    vector<long long> f;
    for (long long d = 2; d * d <= n; d++) {
        while (n % d == 0) {
            f.push_back(d);
            n /= d;
        }
    }
    if (n > 1)
        f.push_back(n);
    return f;
}
 
//------------Dijekstra Algorithm----------------------
void dijekstra(){
	int n, m;
    cin >> n >> m;
    vector<pair<int, int>> v[n];
    int dis[n];
    int par[n];
    int x, y, z;
    for (int i = 0; i < m; i++)
    {
        cin >> x >> y >> z;
        x--;
        y--;
        v[x].push_back({z, y});
        v[y].push_back({z, x});
    }
    for (int i = 0; i < n; i++)
    {
        dis[i] = inf;
        par[i] = i;
    }
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push({0, 0});
    dis[0] = 0;
    while (!pq.empty())
    {
        auto p = pq.top();
        int xi = p.second;
        int xv = p.first;
        pq.pop();
        if (xv > dis[xi])
            continue;
        for (int i = 0; i < sz(v[xi]); i++)
        {
            int yi = v[xi][i].second;
            int yv = v[xi][i].first;
            if (dis[yi] <= xv + yv)
                continue;
            dis[yi] = xv + yv;
            par[yi] = xi;
            pq.push({dis[yi], yi});
        }
    }
    if (dis[n - 1] < inf)
    {
        vector<int> a;
        int ind = n - 1;
        while (ind != par[ind])
        {
            a.push_back(ind);
            ind = par[ind];
        }
        a.push_back(0);
        for (int i = sz(a) - 1; i >= 0; i--)
        {
            cout << a[i] + 1 << ' ';
        }
    }
    else
        cout << -1;
}
//----------------------------------solve function-----------------------------------
 
void solve(){
	
	int n;
	cin>>n;
	int arr[n];
	for(int i=0;i<n;i++) cin>>arr[i];
	int time[n];
	for(int i=0;i<n;i++){
		int left=0,right=0;
		if(i-1>=0){
			left=max(1ll*0,arr[i-1]-arr[i]+1);
		}
		if(i+1<n){
			right=max(1ll*0,arr[i+1]-arr[i]+1);
		}
		time[i]=left+right;
		//cout<<time[i]<<" ";
	}
	//cout<<endl;
	int k=n/2;
	if(n%2!=0) k++;
	
	
	
	 int dp[2505][5001]={INT_MAX};
	 
	 
	for(int j=2;j<=k;j++)
	{
		for(int i=0;i<n;i++)
		{
		dp[j][i]=INT_MAX;
		}
		
	}
		
		
	for(int i=0;i<n;i++) 
	{
		dp[1][i]=time[i];
	}
	
// 	
	for(int j=2;j<=k;j++){
		int mx=INT_MAX;
		for(int i=0;i<n;i++){
			//int y=INT_MAX,x=INT_MAX,z=INT_MAX;
			if(i-2>=0) {
				int x=0;
				int h=max(arr[i-2],arr[i]);
				h--;
				x=max(1ll*0,arr[i-1]-h);
				if(dp[j-1][i-2]!=INT_MAX)
				dp[j][i]=min(dp[j][i],dp[j-1][i-2]+time[i]-x);
			}
			if(mx!=INT_MAX)
			dp[j][i]=min(dp[j][i],mx+time[i]);
			if(i-2>=0){
				mx=min(mx,dp[j-1][i-2]);
			}
 			
			
		 }
	 }
	
	for(int j=1;j<=k;j++){
		int ans=INT_MAX;
		for(int i=0;i<n;i++){
			//cout<<dp[j][i]<<" ";
			ans=min(ans,dp[j][i]);
		}
		//cout<<endl;
		cout<<ans;
		if(j!=k) cout<<" ";
	}
	//cout<<"pk"<<endl;
}
 
int32_t main(){
    IO; 
    int t=1;
    //cin>>t;
    while(t--){
    	solve();
    }
    return 0;
}