2014
03-09

After winning two coupons for the largest shopping mart in your city, you can’t wait inviting your girlfriend for gift hunting. Having inspected hundreds of kinds of souvenirs, toys and cosmetics, you finally narrowed down the candidate list to only n gifts, numbered 1 to n. Each gift has a happiness value that measures how happy your girlfriend would be, if you get this gift for her. Some of them are special – you must get it for your girlfriend (note that whether a gift is special has nothing to do with its happiness value).

Coupon 1 can be used to buy gifts with total price not greater than V1 (RMB). Like most other coupons, you can’t get any money back if the total price is strictly smaller than V1. Coupon 2 is almost the same, except that it’s worth V2. Coupons should be used separately. That means you cannot combine them into a super-coupon that’s worth V1+V2. You have to divide the gifts you choose into two part, one uses coupon 1, the other uses coupon 2.

It is your girlfriend’s birthday today. According to the rules of the mart, she can take one (only one) gift for FREE! Here comes your challenge: how to make your girlfriend as happy as possible?

There will be at most 20 test cases. Each case begins with 3 integers V1, V2 and n (1 <= V1 <= 500, 1 <= V2 <= 50, 1 <= n <= 300), the values of coupon 1 and coupon 2 respectively, and the number of candidate gifts. Each of the following n lines describes a gift with 3 integers: P, H and S, where P is the price, H is the happiness (1 <= P,H <= 1000), S=1 if and only if this is a special gift – you must buy it (or get it for free). Otherwise S=0. The last test case is followed by V1 = V2 = n = 0, which should not be processed.

There will be at most 20 test cases. Each case begins with 3 integers V1, V2 and n (1 <= V1 <= 500, 1 <= V2 <= 50, 1 <= n <= 300), the values of coupon 1 and coupon 2 respectively, and the number of candidate gifts. Each of the following n lines describes a gift with 3 integers: P, H and S, where P is the price, H is the happiness (1 <= P,H <= 1000), S=1 if and only if this is a special gift – you must buy it (or get it for free). Otherwise S=0. The last test case is followed by V1 = V2 = n = 0, which should not be processed.

3 2 4
3 10 1
2 10 0
5 100 0
5 80 0
3 2 4
3 10 1
2 10 0
5 100 0
5 80 1
0 0 0

Case 1: 120

Case 2: 100

#include<stdio.h>
#include<string.h>
#include<algorithm>
using std::sort;
#define inf -2100000000
#define MAXV1 501
#define MAXV2 51
#define MAXN 301
struct T
{
int p,v,f;
bool operator < (const T a) const
{
return f>a.f;
}
int res[MAXV1][MAXV2][2];
inline int max (int a,int b,int c=0,int d=0)
{
return (a>b?a:b)>(c>d?c:d)?(a>b?a:b):(c>d?c:d);
}
int main()
{
int v1,v2,n,i,j,k,m,ts;
int cas=1;
while (scanf("%d%d%d",&v1,&v2,&n))
{
if (v1==0&&v2==0&&n==0) break;
memset(res,0,sizeof(res));
ts=0;
for (i=1; i<=n; ++i)
{
}
for (k=1; k<=n; ++k)
{
for (i=v1; i>=0; --i)
{
for (j=v2; j>=0; --j)
{
{
}
{
}
{
}
else
{
}
}
}
}
m=0;
if (res[v1][v2][1]<ts&&res[v1][v2][0]<ts) m=-1;
if (m==0)
{
for (; k<=n; ++k)
{
for (i=v1; i>=0; --i)
{
for (j=v2; j>=0; --j)
{
}
}
}
for (i=1; i<=v1; ++i)
{
for (j=1; j<=v2; ++j)
{
m=max(m,res[i][j][0],res[i][j][1]);
}
}
}
printf("Case %d: %d/n/n",cas++,m);
}
return 0;
}