http://codeforces.com/contest/366/problem/C
转化为背包问题，可以将a[i]-b[i]*k看成重量,a[i]为价值； 因为a[i]-b[i]*k可以为负数，所以应该分开讨论。结果就是dp[10000],如果等于0则输出-1，否则输出dp[10000];
#include <cstdio>
#include <cstring>
#include <algorithm>
#define maxn 500005
using namespace std; int a[maxn],b[maxn];
int w[maxn];
int dp[maxn];
int n,k; int main()
{
while(scanf("%d%d",&n,&k)!=EOF)
{
for(int i=; i<=n; i++)
{
scanf("%d",&a[i]);
}
for(int i=; i<=n; i++)
{
scanf("%d",&b[i]);
}
for(int i=; i<=n; i++)
{
w[i]=a[i]-b[i]*k;
}
memset(dp,-,sizeof(dp));
dp[]=;
for(int i=; i<=n; i++)
{
if(w[i]>=)
{
for(int j=; j>=w[i]; j--)
{
if(dp[j-w[i]]!=-)
dp[j]=max(dp[j],dp[j-w[i]]+a[i]);
}
}
else
{
for(int j=; j<; j++)
{
if(dp[j-w[i]]!=-)
dp[j]=max(dp[j],dp[j-w[i]]+a[i]);
}
}
}
if(dp[]==) printf("-1\n");
else printf("%d\n",dp[]);
}
return ;
}