fork download
copy 
  1. #include<unordered_map>
  2. #include<unordered_set>
  3. #include<functional>
  4. #include<algorithm>
  5. #include<iostream>
  6. #include<hash_map>
  7. #include<iterator>
  8. #include<iomanip>
  9. #include<numeric>
  10. #include<cstring>
  11. #include<vector>
  12. #include<bitset>
  13. #include<string>
  14. #include<deque>
  15. #include<stack>
  16. #include<queue>
  17. #include<array>
  18. #include<cmath>
  19. #include<list>
  20. #include<map>
  21. #include<set>
  22.  
  23. #include <ext/pb_ds/assoc_container.hpp>
  24. #include <ext/pb_ds/tree_policy.hpp>
  25.  
  26. using namespace __gnu_pbds;
  27. using namespace std;
  28.  
  29. typedef long long ll;
  30. typedef unsigned long long ull;
  31. typedef double db;
  32. typedef long double ldb;
  33.  
  34. #define ordered_set tree<ll, null_type,less_equal<ll>, \
  35. rb_tree_tag,tree_order_statistics_node_update>
  36. #define pii pair<int,int>
  37. #define pll pair<ll,ll>
  38. #define inf INT32_MAX
  39. #define linf INT64_MAX
  40. #define pf push_front
  41. #define pb push_back
  42. #define ppb pop_back
  43. #define ppf pop_front
  44. #define ff first
  45. #define ss second
  46. /*ACPC 2021 ISA-*/
  47. ll fastPow(ll n,ll k/*,ll m*/){
  48.     if(k==0)return 1;
  49.  
  50.     ll res=fastPow(n,k/2/*,m*/)/*%m*/;
  51.  
  52.     res=(res*res)/*%m*/;
  53.  
  54.     if(k&1)res=(res*n)/*%m*/;
  55.  
  56.     return res/*%m*/;
  57. }
  58. ll calcMod(ll a,ll m){
  59.     return (a%m+m)%m;
  60. }
  61. const ll mod=1e9+7,N=1000+5,M=100+5,K=30+5;
  62. int n,m,v[N],w[N],a[M],dp[N][K];
  63. int rec(int i,int j){
  64.     if(i==n)return 0;
  65.  
  66.     if(dp[i][j]!=-1)return dp[i][j];
  67.  
  68.     dp[i][j]=rec(i+1,j);
  69.  
  70.     if(w[i]<=j)dp[i][j]=max(dp[i][j],v[i]+rec(i+1,j-w[i]));
  71.  
  72.     return dp[i][j];
  73. }
  74. bool solve(){
  75.     memset(dp,-1,sizeof(dp));
  76.     cin>>n;
  77.     for(int i=0;i<n;++i){
  78.         cin>>v[i]>>w[i];
  79.     }
  80.     cin>>m;
  81.     for(int i=0;i<m;++i){
  82.         cin>>a[i];
  83.     }
  84.     int ans=0;
  85.     for(int i=0;i<m;++i){
  86.         ans+=rec(0,a[i]);
  87.     }
  88.     cout<<ans<<"\n";
  89. }
  90. int main(){
  91.     ios_base::sync_with_stdio(false);
  92.     cin.tie(nullptr);
  93.  
  94.     int t=1;
  95.     cin>>t;
  96.     while(t--){
  97.         solve();
  98.     }
  99.     return 0;
  100. }
Runtime error #stdin #stdout 0.01s 5596KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/HwlhXn
language:
C++14 (gcc 8.3)
created:
2 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!