I am trying to solve MENUon SPOJ.
My dp state contains solve(days,budget,prev_dish,cnt_prev_dishes).

But I am continously getting wrong answer any help :)

#include<cstdio>
#include<iostream>
#include<cstring>
#define INF 1000000000
using namespace std;
int k,n,m;
long long dp[51][150][51][51],mm[51][150][51];
int c[51],v[51],pr=-1;
long long solve(int k,int B,int prev,int cnt)
{
	if(B<0)return -INF;
	if(B==0 and k>0)return -INF;
	if(k==0)return 0;
	if(dp[k][B][prev][cnt]!=-1)return dp[k][B][prev][cnt];
	long long ans=-INF,idx=-1,diff=-1;
	for(int i=0;i<n;i++)
	{
		if(prev!=i)
		{
			int tmp=solve(k-1,B-c[i],i,1);
			diff=v[i]-c[i];
			if(tmp!=-INF)
			{
				if(tmp+v[i]>ans)
				{
				ans=tmp+v[i];
				idx=i;
				}
				else if(tmp+v[i]==ans)
				{
					if((v[i]-c[i])>(v[idx]-c[idx]))
					idx=i;
				}
			}
		}
		else
		{
			int val=v[i]/2;
			if(cnt>1)val=0;
			int tmp=solve(k-1,B-c[i],i,cnt+1);
			if(tmp!=-INF)
			{
				if(tmp+val>=ans)
				{
				ans=tmp+val;
				idx=i;
				}
			}
		}
	}
	mm[k][B][prev]=idx;
	pr=idx;
	return dp[k][B][prev][cnt]=ans;
}
void recurse(int k,int B,int pre)
{
    if(k==0)return;
    else
    {
        int x=mm[k][B][pre];
        recurse(k-1,B-c[x],x);
         cout<<x+1<<" ";
    }
}
int main()
{
	cin>>k>>n>>m;
	while(k|n|m)
	{
		memset(dp,-1,sizeof dp);
		memset(mm,-1,sizeof mm);
		long long ans=-INF;
		for(int i=0;i<n;i++)
		{
			cin>>c[i]>>v[i];
			v[i]<<=1;
		}
		double x=solve(k,m,-1,0);
		if(x<=0)
		cout<<"0.0"<<endl;
		else
		{
						printf("%.1lf\n",x/2);
            recurse(k-1,m-c[pr],pr);
             cout<<pr+1;
    }
    cout<<endl;
		cin>>k>>n>>m;
	}
}