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]);