DP Problem (IPL) doesn't pass 2 test cases

Question

Here's the problem IPL : http://www.iarcs.org.in/inoi/2014/zco2014/zco2014-2b.php

---

In IPL 2025, the amount that each player is paid varies from match to match. The match fee depends on the quality of opposition, the venue etc.

The match fees for each match in the new season have been announced in advance. Each team has to enforce a mandatory rotation policy so that no player ever plays three matches in a row during the season.

Nikhil is the captain and chooses the team for each match. He wants to allocate a playing schedule for himself to maximize his earnings through match fees during the season.

Input format

Line 1: A single integer N, the number of games in the IPL season.

Line 2: N non-negative integers, where the integer in position i represents the fee for match i.

Output format

The output consists of a single non-negative integer, the maximum amount of money that Nikhil can earn during this IPL season.

Test data

There is only one subtask worth 100 marks. In all inputs:

1 ≤ N ≤ 2×10^5

The fee for each match is between 0 and 10^4, inclusive.

Live evaluation data

There are 12 test inputs on the server during the exam.

Limits

Time limit : 1s

Memory limit: 32 MB

---

I have included all of my logic for the DP in the code itself, so I am not mentioning the logic seperately. 10 test cases get through properly while the remaining 2 test cases (2nd and somewhere in between) show WA though I think the logic is fine. Maybe there's some edge case/base case I am missing out.

Here's the code below (Ideone link : https://ideone.com/pPZFPJ)

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int N; cin>>N;
    int arr[N];
    for (int i=0; i<=N-1; i++) cin>>arr[i];

    int dp[N][3];

    // dp[i][0]=max money on day i s.t he charges on day i,i-1
    // dp[i][1]=max money on day i s.t he charges on day i,i-2
    // dp[i][2]=max money on day i s.t he charges on day i,i-3

    dp[0][0] = arr[0]; dp[1][1]=arr[1];
    dp[1][0] = arr[0]+arr[1]; //second day
    dp[2][0] = arr[1]+arr[2]; dp[2][1] = arr[0]+arr[2]; dp[2][2] = 0;

    for (int i=3; i<N; ++i) {
    dp[i][0] = arr[i] + max(dp[i-1][1],dp[i-1][2]);
    dp[i][1] = arr[i] + max(dp[i-2][0],dp[i-2][1]);
    dp[i][2] = arr[i] + dp[i-3][0];
    }

    cout<<max(max(dp[N-1][0],dp[N-1][1]),dp[N-1][2])<<endl;

    /*for (int i=0; i<=N-1; i++)
    {
        for (int j=0; j<=2; ++j)
        cout<<dp[i][j] << "   ";
        cout<<endl;
    }*/
}

/*1 2 3 4 5 6 7 8 9.... i-5 i-4 i-3 i-2 i-1 i i+1 i+2 i+3 ..... N*/

Just a note, in case whoever is typing is familiar in some other language, please write the code in something between C,C++,Java otherwise, it might be hard for me to understand. Pseudo-codes are equally fine for me but please do state the base cases. Also, I do not wish to alter the logic of the DP since I am aware of 2 easier DP solutions (and they have passed properly).

Answer 1

The error has been rectified. The output assumed that the guy will charge on the last day which isn't a necessity. So, dp[N-2][0] should've been there among the the max(a,b,c,..) term.