Guest User

Untitled

a guest
Jul 11th, 2016
302
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.83 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. #define icin(x) scanf("%d",&x)
  4. #define pb push_back
  5. #define LL long long
  6. #define F first
  7. #define S second
  8. #define eps ((double)1e-14)
  9. #define maxn 109
  10. #define maxm 100009
  11.  
  12. using namespace std;
  13.  
  14. int dp[15][500000];
  15. int mus[15][15];
  16. int cost[15][15];
  17. int sum_cost[15][15];
  18. int curl[15],maxl[15];
  19.  
  20. int main()
  21. {
  22.   int t;
  23.   icin(t);
  24.   for(int tc=1;tc<=t;tc++)
  25.   {
  26.     int m,n;
  27.     icin(m);
  28.     icin(n);
  29.     memset(dp,-1,sizeof(dp));
  30.     memset(sum_cost,0,sizeof(sum_cost));
  31.     int init=0;
  32.     for(int i=1;i<=n;i++)
  33.     {
  34.       icin(maxl[i]);
  35.       icin(curl[i]);
  36.       for(int j=1;j<=maxl[i];j++)
  37.         icin(mus[i][j]);
  38.       init += mus[i][curl[i]];
  39.       for(int j=2;j<=maxl[i];j++)
  40.       {
  41.         icin(cost[i][j]);
  42.         sum_cost[i][j] = sum_cost[i][j-1] + cost[i][j];
  43.       }
  44.     }
  45.  //  cout << "OUT" << init << endl;
  46.     for(int i=0;i<=init;i++)
  47.       dp[0][init]=0;
  48.     for(int i=1;i<=8;i++)
  49.     {
  50.       for(int j=curl[i]+1;j<=maxl[i];j++)
  51.       {
  52.         //cout << i << " " << j << endl;
  53.         int mm = sum_cost[i][j] - sum_cost[i][curl[i]];
  54.         int mp = mus[i][j] - mus[i][curl[i]];
  55.         for(int k=0;k<=100000;k++)
  56.         {
  57.           if(dp[i-1][k]!=-1)
  58.           {
  59.             if(dp[i][k+mp]==-1)
  60.               dp[i][k+mp] = dp[i-1][k] + mm;
  61.             else
  62.               dp[i][k+mp] = min(dp[i][k+mp],dp[i-1][k]+mm);
  63.           }
  64.         }
  65.  
  66.       }
  67.       for(int k=0;k<=100000;k++)
  68.       {
  69.         if(dp[i][k]==-1)
  70.           dp[i][k]=dp[i-1][k];
  71.         else if(dp[i-1][k]!=-1)
  72.           dp[i][k] = min(dp[i-1][k],dp[i][k]);
  73.       }
  74.     }
  75.  
  76.     int ans =0,x;
  77.     for(int i=0;i<=100000;i++)
  78.     {
  79.       if(dp[8][i]<=m && dp[8][i]!=-1)
  80.       {
  81.         ans=i;
  82.         x = dp[8][i];
  83.       }
  84.     }
  85.     printf("Case #%d: %d\n",tc,ans);
  86.   }
  87. }
Add Comment
Please, Sign In to add comment