abhishekjoshi
May '13

Please look at the following problem
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=10959
I have used Dynamic Programming similar to what is shown to be correct here
http://community.topcoder.com/tc?module=Static&d1=match_editorials&d2=srm26114
Corresponding problem statement(just a little modification that capacity is apart from the weight of the box.)
http://community.topcoder.com/stat?c=problem_statement&pm=4660&rd=79953
Can anyone please tell what is wrong in the following code, on which test case it might fail? Any help would be appreciated.
sum_of_stack[i] contains for ith turtle what is the min. total weight of the stack of turtles can it support with the ith turtle in bottom.
max_height[i] contains for the ith turtle what is the max height we can achieve with the ith turtle in bottom of the stack.

#include <stdio.h>
#include <stdlib.h>
#include<cstring>
#include<iostream>
using namespace std;
typedef long long int ll;
struct node
{
    ll w,s;
};
struct node node[5608];
int compare (const void * a, const void * b)
{
  return ( (*(struct node *)a).s - (*(struct node *)b).s );
}
int main(int argc, char* argv[])
{
        int k=0;
        while(!feof(stdin))
        {
                //scanf("%d%d",&(node[k].w),&(node[k].s));
                cin>>node[k].w>>node[k].s;
                k++;
        }
        qsort(node,k,sizeof(struct node),compare);
        ll sum_of_stack[5608];
        int max_height[5608];
        for(int i=0;i<k;i++)
        {
                max_height[i]=1;
                sum_of_stack[i]=node[i].w;
        }
        for(int i=0;i<k;i++)
        {
                for(int j=0;j<i;j++)
                {
                        if(max_height[i]<(max_height[j]+1))
                        {
                                if((sum_of_stack[j]+node[i].w)<=node[i].s)
                                {
                                        max_height[i]=(max_height[j]+1);
                                        sum_of_stack[i]=sum_of_stack[j]+node[i].w;
                                }
                        }
                        else if(max_height[i]==(max_height[j]+1))
                        {
                                if((sum_of_stack[j]+node[i].w)<=sum_of_stack[i])
                                {
                                        sum_of_stack[i]=sum_of_stack[j]+node[i].w;
                                }
                        }
                }
                //printf("%lld and %d\n",sum_of_stack[i],max_height[i]);
        }
        int max=1;
        for(int i=0;i<k;i++)
        {
                if(max<max_height[i])
                {
                        max=max_height[i];
                }
        }
        printf("%d\n",max);
        return 0;
}

Thanks