ENG  RUS Timus Online Judge
Online Judge
Problems
Authors
Online contests
Site news
Webboard
Problem set
Submit solution
Judge status
Guide
Register
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

## Discussion of Problem 1570. Eating High

Can anyone tell me what's the problem with test 9
Posted by lakeoffire 31 Oct 2007 18:32
Re: Can anyone tell me what's the problem with test 9
Posted by lakeoffire 6 Nov 2007 15:34
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;
}

{
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);

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;
}