比赛 2020级再出发之位运算 评测结果 AAAAAATTTT
题目名称 买表(民间数据) 最终得分 60
用户昵称 宇战 运行时间 8.214 s
代码语言 C++ 内存使用 0.00 MiB
提交时间 2023-07-25 18:11:05
显示代码纯文本
    #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;     
    }