Runtime error for dp problem Princess Farida on Spoj

I had been trying to solve these problem from last three hours but I am not able to find where my code is giving tle . Please help to find where I am wrong.

Here is the problem:

Here is my code:

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

int main() {
	// your code goes here
	ll t;
	cin>>t;
	ll k=1;
	while(t--)
	{
		ll n;
		cin>>n;
		vector<ll>arr;
		for(int i=0;i<n;i++)
		{
			ll num;
			cin>>num;
			arr.push_back(num);
		}
		ll dp[10000];
		dp[0] = 0;
		dp[1]=arr[0];
		if(n == 0)
		{
			printf("Case %d: %d\n",k,0);
		}
		if(n == 1)
		{
			printf("Case %d: %lld\n",k,dp[1]);
			continue;
		}
		dp[2] = max(arr[1],arr[2]);
		for(ll i=3;i<=n;i++)
		{
			dp[i] = max(arr[i-1]+dp[i-2],dp[i-1]);
		}
	   printf("Case %d: %lld\n",k,dp[n]);
	   k++;
	}
	
	return 0;
}

Thanks :slight_smile:

Can u please help @ssrivastava990,
@carre

I see a lot of problems-

1
for(int i=0;i<n;i++)
You earlier declared n as ll
2
ll dp[10000];
Size of the array
What if n=10000?
3
if(n == 0)
{
	printf("Case %d: %d\n",k,0);
}
I bet you didn't even test it on this case.
4
if(n == 1)
{
	printf("Case %d: %lld\n",k,dp[1]);
	continue;
}
data type of k. Same above and everywhere else.
5
dp[2] = max(arr[1],arr[2]);
Wrong indexing

Your code gives wrong answers on samples. I believe you should try to debug it yourself first.

Edit- It gives correct answer on samples on codechef ide. That is certainly due to compiler differences.

2 Likes

Here is code updated code as per your suggestions :

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

int main() {
	// your code goes here
	int t;
	cin>>t;
	for(int i=1;i<=t;i++)
	{
		int n;
		cin>>n;
		vector<ll>arr;
		for(int i=0;i<n;i++)
		{
			ll num;
			cin>>num;
			arr.push_back(num);
		}
		vector<ll>dp(10001);//max no of monsters
		if(n == 0)
		{
			printf("Case %d: %d\n",i,0);
			continue;
		}
	    dp[0] = 0;//case when there are no monster
	    dp[1] = arr[0];//case when is there is only one monster
	//dp[2] = max(arr[1]+dp[0],dp[1]); 
	    for(int i=2;i<=n;i++)
	    {
	    	dp[i] = max(arr[i-1]+dp[i-2],dp[i-1]);//select the maximum one
	    }
	     printf("Case %d: %lld\n",i,dp[n]);
	}
	return 0;
}

Can u plz provide test cases where it is failing? :slight_smile:

Edit : Thank you @akshitm16 my solution is accepted :smiley:

2 Likes