Yes, there is after preliminary DP for min-price-allowed-steps-graph.

There is 30000*100 solution O(filling X dishes)

Limit for dishes is 100. Why __int64 (64 bit) should be better than int (32 bit)? In both cases you need an array, don't you?

3 4
a 4 4
b 1 1
c 3 3

First, DP needs to be 2D. Values array can be 1D, but backtracking info should be 2D. At least I couldn't make it 1D. And even after making parental state indication 2D I still had bugs in that back-traversal :)

about wa 13
i am pretty sure its a problem with backtracking.

5 8
a 11 1.1
b 14 1.4
c 15 1.5
e 15 1.5
f 20 2.0

5 8
a 11 1.1
b 14 1.4
c 15 1.5
e 10 1
f 20 2.0

seems like problem with precision

1).No
because
2).You've got unlimited reserve of dishes. We've got a total number of kinds of dishes.
3). Whats up with Test 13???Last solvings got WA and TL...

This is the first problem in timus fo me when
DP gives TL(Tle15).In all world such strong tests
when DP used are absent as a rule. What parameters we have:
1. productivityness: from 0 to 30000;
2. number of dishes from 1 to 100
3. possible number of each dishes: from 1 to 100
Thus DP needs ~ 300000000 simple integer operations.
Why it leads to TLE.

Edited by author 11.10.2007 13:59

Edited by author 11.10.2007 14:02

This is my code. I would appreciate if someone will help me.

#include <stdio.h>
#include <vector>
#include <string.h>
#include <bitset>
#include <math.h>

using namespace std;

#define INFI 0x3f3f3f3f
#define NMAX 150300
#define pb push_back
#define ff first
#define ss second
#define sz size()

inline int MAX(int a, int b) { return (a > b) ? (a) : (b); }
inline int MIN(int a, int b) { return (a < b) ? (a) : (b); }

typedef struct dish
{
    int f, c;
    char s[50];
};
vector<dish> p;
int n, m;
int a[NMAX], b[NMAX], c[NMAX];
short viz[NMAX], viz2[NMAX];

inline dish scan()
{
    dish aux;
    double x;
    scanf("%s %d %lf\n", aux.s, &aux.c, &x);
    aux.f = (int)floor(x*1000);
    return aux;
}

void read()
{
    scanf("%d %d\n", &n, &m);
    for(int i = 0; i < n; ++i)
        p.pb( scan() );
}

void knap1()
{
    int i, j, until;
    viz[0] = 1;
    for(i = p.sz-1; i >= 0; --i)
    {    for(j = 0; j < NMAX; ++j)
            if(j - p[i].f >= 0 && viz[ j - p[i].f ])
            {
                if(!viz[ j ])
                    a[ j ] = a[ j - p[i].f ] + p[i].c, viz[ j ] = 1;
                else
                    a[ j ] = MIN(a[ j ], a[ j - p[i].f ] + p[i].c);
            }
    }
}

void knap2()
{
    int i, j, until;
    memset(c, -1, sizeof(c));
    viz2[0] = 1;
    for(i = p.sz-1; i >= 0; --i)
        for(j = 0; j < NMAX; ++j)
            if(j - p[i].f >= 0 && viz2[ j - p[i].f ])
            {
                viz2[ j ] = 1;
                if(b[ j - p[i].f ] + (c[ j - p[i].f ] != i) > b[ j  ])
                    b[ j ] = b[ j - p[i].f ] + (c[ j - p[i].f ] != i), c[ j ] = i;
            }
}

int main()
{
//    freopen("1570.in", "r", stdin);
//    freopen("1570.out", "w", stdout);

    read();

    knap1();

    knap2();

    int min = INFI, poz = 0;
    //for(int i = m*1000; i < NMAX; ++i)
    int i = m*1000;
        if(viz[i])
            if(min > a[i] || (min == a[i] && b[i] > b[poz]))
                min = a[i], poz = i;

    printf("%d\n", min);
//      printf("%d\n", b[poz]);
    int j = poz, nr, aux;
    while(j > 0)
    {
        nr = 1;
        aux = c[j];
        j -= p[ c[j] ].f;
        while(c[j] == aux)
               ++nr, j -= p[ aux ].f;
        printf("%s %d\n", p[aux].s, nr);
    }
//     printf("\n");
//     for(j = 0; j < NMAX; ++j)
//          if(b[j]!= 0)
//              printf("%d %d %d %d\n", j, a[j], b[j], c[j]);

    return 0;
}

this line is wrong
if (bcnt[i-b[j].cal][0] >= bcnt[i][0] && bcnt[i-b[j].cal][j] == 0)

delete your code