Advertisement
Guest User

black man penetrate eachoder

a guest
Apr 19th, 2019
128
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.03 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. int dp[2005][1005];
  5. int v[1005][1005];
  6. int main()
  7. {
  8.     freopen("txt.in","r",stdin);
  9.     freopen("txt.out","w",stdout);
  10.     int n,m,tc,k;
  11.     scanf("%d",&tc);
  12.     while(tc--)
  13.     {
  14.         scanf("%d %d",&k,&n);
  15.         for(int i=1; i<=n; ++i)
  16.         {
  17.             scanf("%d",&m);
  18.             v[i][0]=m;
  19.             for(int j=1; j<=m; ++j)
  20.             {
  21.                 scanf("%d",&v[i][j]);
  22.             }
  23.         }
  24.         for(int i=0;i<=k;++i)
  25.         {
  26.             for(int j=0;j<=n;++j)
  27.             {
  28.                 dp[i][j]=-1;
  29.             }
  30.         }
  31.         for(int g=0; g<=k; ++g)
  32.         {
  33.             dp[g][0]=0;
  34.             for(int i=1; i<=n; ++i)
  35.             {
  36.                 for(int j=1; j<=v[i][0]; ++j)
  37.                 {
  38.                     if(g>=v[i][j]&&dp[m-v[i][j]][i-1]!=-1)
  39.                         dp[g][i]=max(dp[g-v[i][j]][i-1]+v[i][j],dp[g][i]);
  40.                 }
  41.             }
  42.  
  43.         }
  44.         dp[k][n]!=-1 ? printf("%d\n",dp[k][n]) : printf("no solution\n");
  45.     }
  46.     return 0;
  47. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement