记录编号	580654	评测结果	AAAAAAAAAA
题目名称	3436.[NOI Online 2020 3rd PJ]买表(民间数据)	最终得分	100
用户昵称	宇战	是否通过	通过
代码语言	C++	运行时间	2.218 s
提交时间	2023-07-25 16:18:18	内存使用	0.00 MiB

    #include<bits/stdc++.h>
    using namespace std;
    int n,m,top=1,mm,v[500010],p[500010],cha[500010],w[500010],dp[500010];
    int main(){
        freopen("noi_online2020_watch.in","r",stdin);
        freopen("noi_online2020_watch.out","w",stdout);
          scanf("%d%d",&n,&m);
          for(int i=1;i<=n;i++){
              cin>>v[i]>>p[i];
          }
          for(int i=1;i<=m;i++){
              cin>>w[i];
              mm=max(mm,w[i]);
          }
          dp[0]=1;
          for(int i=1;i<=n;i++){
              int t=1;
              while(p[i]){
              if(p[i]>=t){
                  p[i]-=t;
                  cha[top]=v[i]*t;
                  top++;
              }else{
                  cha[top]=v[i]*p[i];
                  top++;
                  break;
              }          
              t*=2;
              }
    }
    
              for(int i=1;i<top;i++){
                  for(int j=mm;j>=cha[i];j--){
                      
                      dp[j]=max(dp[j],dp[j-cha[i]]);
                  }
              }
             for(int i=1;i<=m;i++){
                 if(dp[w[i]]){
                     cout<<"Yes"<<endl;
                 }else{
                     cout<<"No"<<endl;
                 }
             } 
          return 0;     
    }