I was solving the 1482E - Skyline Photo, and it turns out to be WA. I am not sure why did this happen please help me out.

I have used a 2D dp array where dp[i][0] stores the maximum beauty that can be achieved if we combine ith building with the last building dp[i][1] stores the maximum beauty that can be achieved if put in a new photo

While storing the value in dp[i][0] I also took note that in some cases using dp[i-1][0] and dp[i-1][1] both may result with same beauty. So, I took the one that had the greater beauty for the smallest building in the last photo cause that will give a better solution if we happen to find a smaller building with better beauty.

for this "combine" I used a 2D mn_idx array that stores for each state the index of building with minimum height in the current photo ending at ith building.

I could not see the testcases, it shows WA on test 8. So is the logic completely wrong (it will be better if you could please explain why is that so?)?

Here is my code

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

using namespace __gnu_pbds;
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> indexed_set;

#define mem(dp,a)           memset(dp,a,sizeof dp)
#define rep(i,a,b)          for(ll i=a;i<b;i++)
#define pb(x)               push_back(x)
#define mp(x,y)             make_pair(x,y)
#define fastio              ios_base::sync_with_stdio(false);cin.tie(NULL)
#define F                   first
#define S                   second
#define all(v)              (v).begin(),(v).end()

const ld pi=3.14159265359;
ll MOD=998244353;
ll mod=1e9+7;
ll INF = 1e18;

int n;
vector<ll> h, b;

int main(){
    
    fastio;
    cin>>n;
    h.assign(n, 0);
    b.assign(n, 0);
    rep(i,0,n)cin>>h[i];
    rep(i,0,n)cin>>b[i];

    vector<vector<ll>> dp(n, vector<ll> (2, -INF));
    ll mn_idx[n][2];
    dp[0][0] = dp[0][1] = b[0];
    mn_idx[0][0] = mn_idx[0][1] = 0;
    rep(i,1,n){
        ll l1 = dp[i-1][0] + (h[mn_idx[i-1][0]] < h[i] ? 0 : -b[mn_idx[i-1][0]] + b[i]);
        ll lb1 = (h[mn_idx[i-1][0]] < h[i] ? b[mn_idx[i-1][0]] : b[i]);
        ll l2 = dp[i-1][1] + (h[mn_idx[i-1][1]] < h[i] ? 0 : -b[mn_idx[i-1][1]] + b[i]);
        ll lb2 = (h[mn_idx[i-1][1]] < h[i] ? b[mn_idx[i-1][1]] : b[i]);
        if(l1 > l2)
            dp[i][0] = l1, mn_idx[i][0] = (l1 == dp[i-1][0] ? mn_idx[i-1][0] : i);
        else if(l2 > l1)
            dp[i][0] = l2, mn_idx[i][0] = (l2 == dp[i-1][1] ? mn_idx[i-1][1] : i);
        else {
            if(lb1 > lb2)
                dp[i][0] = l1, mn_idx[i][0] = (l1 == dp[i-1][0] ? mn_idx[i-1][0] : i);
            else 
                dp[i][0] = l2, mn_idx[i][0] = (l2 == dp[i-1][1] ? mn_idx[i-1][1] : i);
        }
        dp[i][1] = max(dp[i-1][0], dp[i-1][1]) + b[i];
        mn_idx[i][1] = i;
    }
    cout<<max(dp[n-1][0], dp[n-1][1])<<endl;
}

For problem F.....

Why is this solution wrong ? I considered that if the number of terms is even, answer is just sum of odd numbered terms or even numbered terms but if the number of terms is odd, we have to skip one extra element i.e. we need to skip two consecutive elements once. Here, dp[i][0] stores if we haven't performed a move where we have skipped two consecutive terms, dp[i][1] stores if we have performed a move where we have skipped two adjacent terms.

    ll dp[n+1][2];mem(dp,0);
    for(int i=1;i<n+1;i++)dp[i][0]=dp[i][1]=-INF;
    dp[1][0]=a[1];dp[1][1]=0;
    dp[2][0]=a[2];dp[2][1]=0;
    for(int i=3;i<n+1;i++)
    {
        dp[i][0]=max(dp[i-2][0]+a[i],dp[i][0]);
        dp[i][1]=max(dp[i-3][0]+a[i],max(dp[i-2][1]+a[i],dp[i][1]));
    }
    if(i&1)
    cout<<max(dp[n][1],dp[n][0]);
    else cout<<max(dp[n-1][0],dp[n][0]);

This looks intuitively correct to me but is failing on sample test 4

UPD : Found out what the problem was, my friend told me that we can perform either two 1 skips (i.e. removing other than adjacent you are again removing the adjacent element or removing two consecutive elements in a single move) or a single two skip (i.e. remove three consecutive elements) when number of terms are odd. Similarly, you can figure out for even that you can either perform a single 1 skip until nth elment or remove nth element and do not perform any skips until n-1th element.

Consider the case { A1, A2, A3, A4, A5 }, then you can skip A2, A3, A4 and choose only A1, A5 this was the case which I was missing. After adding this to the solution, correct code goes somewhat like this

    ll dp[n+1][3];mem(dp,0);
    rep(i,0,n+1)dp[i][0]=dp[i][1]=dp[i][2]=-INF;
    dp[1][0]=a[1];
    dp[2][1]=a[2];
    dp[3][0]=a[1]+a[3];dp[3][2]=a[3];
    rep(i,4,n+1){
        dp[i][0]=max(dp[i-2][0]+a[i],dp[i][0]);
        dp[i][1]=max({dp[i-3][0]+a[i],dp[i-2][1]+a[i],dp[i][1]});
        dp[i][2]=max({dp[i-4][0]+a[i],dp[i-3][1]+a[i],dp[i-2][2]+a[i],dp[i][2]});
    }
    if(n&1)cout<<max({dp[n][2],dp[n-1][1],dp[n-2][0]});
    else cout<<max(dp[n][1],dp[n-1][0]);