HDU 5445 Food Problem

Problem Description

Few days before a game of orienteering, Bell came to a mathematician to solve a big problem. Bell is preparing the dessert for the game. There are several different types of desserts such as small cookies, little grasshoppers and tiny mantises. Every type of dessert may provide different amounts of energy, and they all take up different size of space.

Other than obtaining the desserts, Bell also needs to consider moving them to the game arena. Different trucks may carry different amounts of desserts in size and of course they have different costs. However, you may split a single dessert into several parts and put them on different trucks, then assemble the parts at the game arena. Note that a dessert does not provide any energy if some part of it is missing.

Bell wants to know how much would it cost at least to provide desserts of a total energy of 

p

Input

T(T≤10) representing the number of test cases.

For each test case there are three integers 

n,m,p on the first line 

(1≤n≤200,1≤m≤200,0≤p≤50000), representing the number of different desserts, the number of different trucks and the least energy required respectively.

The 

i−th of the 

n following lines contains three integers 

ti,ui,vi(1≤ti≤100,1≤ui≤100,1≤vi≤100) indicating that the 

i−th dessert can provide 

tienergy, takes up space of size 

ui and that Bell can prepare at most 

vi of them.

On each of the next 

m lines, there are also three integers 

xj,yj,zj(1≤xj≤100,1≤yj≤100,1≤zj≤100) indicating that the 

j−th truck can carry at most size of 

xj , hiring each one costs 

yj and that Bell can hire at most 

zj

Output

50000. Otherwise, output 

TAT

Sample Input

4

1 1 7

14 2 1

1 2 2

1 1 10

10 10 1

5 7 2

5 3 34

1 4 1

9 4 2

5 3 3

1 3 3

5 3 2

3 4 5

6 7 5

5 3 8

1 1 1

1 2 1

1 1 1

Sample Output

4

14

12

TAT

#include<cstdio>
#include<cstring>
#include<ctime>
#include<algorithm>
using namespace std;
const int maxn = 100001;
int n,T,f[maxn],m,p;

struct cake
{
    int x,y,z;
    void read(){scanf("%d%d%d",&x,&y,&z);}
}a[maxn];

int main()
{
    scanf("%d",&T);
    while (T--)
    {
        scanf("%d%d%d",&n,&m,&p);
        memset(f,-1,sizeof(f));
        f[0]=0;
        int flag=1,ans;
        for (int i=0;i<n;i++) 
        {
            a[i].read();
            int u,v;
            for (int j=1;j<=a[i].z;j<<=1)
            {
                a[i].z-=j;
                u=a[i].x*j;
                v=a[i].y*j;
                for (int k=p+100;k>=u;k--)
                if (f[k-u]>=0)
                {
                    if (f[k]>=0) f[k]=min(f[k],f[k-u]+v);
                    else f[k]=f[k-u]+v;
                }
            }
            if (a[i].z)
            {
                u=a[i].x*a[i].z;
                v=a[i].y*a[i].z;
                for (int k=p+100;k>=u;k--)
                if (f[k-u]>=0)
                {
                    if (f[k]>=0) f[k]=min(f[k],f[k-u]+v);
                    else f[k]=f[k-u]+v;
                }
            }
        }
        ans=-1;
        for (int i=p;i<=p+200;i++)
        {
            if (ans==-1) ans=f[i];
            if (f[i]!=-1) ans=min(ans,f[i]);
        }
        if (ans==-1) flag=0;
        if (flag) {
            memset(f,0,sizeof(f));
            p=50000;
        }
        for (int i=0;i<m;i++) 
        {
            a[i].read();
            if (!flag) continue;
            int u,v;
            for (int j=1;j<=a[i].z;j<<=1)
            {
                a[i].z-=j;
                u=a[i].y*j;
                v=a[i].x*j;
                for (int k=p;k>=u;k--) f[k]=max(f[k],f[k-u]+v);
            }
            if (a[i].z)
            {
                u=a[i].y*a[i].z;
                v=a[i].x*a[i].z;
                for (int k=p;k>=u;k--) 
                {
                    f[k]=max(f[k],f[k-u]+v);
                    if (f[k]>=ans) p=k;
                }
            }
        }
        if (flag)
            for (int i=0;i<=p;i++) 
                if (f[i]>=ans) {ans=i; flag=1; break;}
                else flag=0;    
        if (flag) printf("%d\n",ans);
        else printf("TAT\n");
    }
    return 0;
}