poj 3900 The Robbery

poj 3900 The Robbery

#include<cstdio>#include<cstring>#include<cmath>#include<algorithm>using namespace std;struct node{    long long value;    long long weight;    int num;}box[20];int n;long long m;long long ans;long long sum[20];      bool cmp(const node &a,const node &b)   {return a.value*1.0/a.weight>b.value*1.0/b.weight;}inline bool cut(int pos,long long value,long long left){    if(pos==n+1) return true;if(value+sum[pos]<=ans) return true; double best=(box[pos].value*1.0/box[pos].weight);       if(value+(long long)ceil(best*left)<=ans) return true;      return false;}void dfs(int pos,long long value,long long left){    ans=max(ans,value);    if(cut(pos,value,left)) return; for(int i=box[pos].num;i>=0;i--){       if(left-box[pos].weight*i<0) continue;          dfs(pos+1,value+box[pos].value*i,left-box[pos].weight*i);    }}int main(){    int cas;    long long sumv;    long long sumw;    scanf("%d",&cas);    while(cas--)    {        ans=0;        sumv=sumw=0;        scanf("%d%lld",&n,&m);        for(int i=1;i<=n;i++)        { scanf("%lld",&box[i].weight); sumw+=box[i].weight*i;        }        for(int i=1;i<=n;i++)        { scanf("%lld",&box[i].value); box[i].num=i; sumv+=box[i].value*i;        }        if(sumw<=m)        { printf("%lldn",sumv); continue;        }        sort(box+1,box+1+n,cmp);        sum[n+1]=0;        for(int i=n;i>=1;i--)        { sum[i]=sum[i+1]+box[i].value*box[i].num;        }        dfs(1,0,m);        printf("%lldn",ans);    }    return 0;}