Codeforce 366C. Dima and Salad

[DP]
第一次用Custom test AC題目 XDD
這應該是NP問題："子集合和=0"

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define BASE 100000
int jz[BASE+20000];
int tmp[BASE+20000];
void set(int a,int v)
{
    //printf("set(%d %d),jz[%d]=%d\n",a,v,a,jz[a]);
    if(v>jz[a+BASE])
        jz[a+BASE]=v;
}
int get(int a)
{
    return jz[a+BASE];
}
void setmp(int a,int v)
{
    //printf("set(%d %d),jz[%d]=%d\n",a,v,a,jz[a]);
    if(v>tmp[a+BASE])
        tmp[a+BASE]=v;
}
int getmp(int a)
{
    return tmp[a+BASE];
}
void resetmp()
{
    for(int lx=0;lx<BASE+20000;lx++)
        tmp[lx]=-1;
}
void write()
{
    for(int lx=0;lx<BASE+20000;lx++)
        jz[lx]=tmp[lx];
}
int main()
{
    int n,k;
    resetmp();
    for(int lx=0;lx<BASE+20000;lx++)
        jz[lx]=-1;
    scanf("%d %d",&n,&k);
    set(0,0);
    int a[110],b[110];
    for(int lx=0;lx<n;lx++)
        scanf("%d",a+lx);
    for(int lx=0;lx<n;lx++)
    {
        scanf("%d",b+lx);
        b[lx]*=k;
    }
    for(int lx=0;lx<n;lx++)
    {
        for(int ly=-BASE;ly<=10010;ly++)
        {
           int v=get(ly);
           setmp(ly,v);
           if(v>=0)
           {
               setmp(ly+a[lx]-b[lx],v+a[lx]);
               //printf("visit(%d)\n",ly);
           }   
        }
        write();
        resetmp();
    }
    if(get(0)==0)
        printf("-1\n");
    else
        printf("%d\n",get(0));
    return 0;
}