C - Coin Change (III)
Time Limit:2000MS Memory Limit:32768KB 64bit IO Format:%lld & %llu
Description
In a strange shop there are n types of coins of value A, A ... A. C, C, ... C denote the number of coins of value A, A ... Arespectively. You have to find the number of different values (from 1 to m), which can be produced using these coins.
Input
Input starts with an integer T (≤ 20), denoting the number of test cases.
Each case starts with a line containing two integers n (1 ≤ n ≤ 100), m (0 ≤ m ≤ 10). The next line contains 2n integers, denoting A, A... A, C, C ... C (1 ≤ A ≤ 10, 1 ≤ C ≤ 1000). All A will be distinct.
Output
For each case, print the case number and the result.
Sample Input
2
3 10
1 2 4 2 1 1
2 5
1 4 2 1
Sample Output
Case 1: 8
Case 2: 4
#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;
#define mod 100000007
int a[],c[],dp[],b[];
int main()
{
int n,k,t,i,j,r;
scanf("%d",&t);
for(i=; i<=t; i++)
{
memset(dp,,sizeof(dp));
scanf("%d%d",&n,&k);
for(j=; j<=n; j++)scanf("%d",&b[j]);
for(j=; j<=n; j++)scanf("%d",&c[j]);
int nu=,re,rs;
for(j=; j<=n; j++)
{
re=b[j],rs=c[j];
c[j]*=b[j];
while(rs)
{
if(re<c[j])
a[nu++]=re,c[j]-=re;
else a[nu++]=c[j];
rs>>=;
re<<=;
}
}
for(j=; j<nu; j++)
{
for(r=k; r>=; r--)
{
if(dp[r]&&r+a[j]<=k)
dp[r+a[j]]=;
if(r==&&a[j]<=k)
dp[a[j]]=;
} }
int sum=;
for(r=; r<=k; r++)sum+=dp[r];
cout<<"Case "<<i<<": ";
cout<<sum<<endl;
} }