Guest User

Untitled

a guest
Jul 11th, 2016
341
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.63 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. #define icin(x) scanf("%d",&x)
  4. #define lcin(x) scanf("%lld",&x)
  5. #define pb push_back
  6. #define LL long long
  7. #define F first
  8. #define S second
  9. #define eps ((double)1e-14)
  10. #define maxn 109
  11. #define maxm 100009
  12. #define bc(x) __builtin_popcount(x);
  13.  
  14. using namespace std;
  15.  
  16.  
  17. LL mus[15][15];
  18. LL cost[15][15];
  19. LL sum_cost[15][15];
  20. int curl[15],maxl[15];
  21. vector<int> idx1,idx2;
  22. map<LL,LL> m1,m2;
  23. LL m;
  24. int n;
  25.  
  26. void f(int pos,LL cur_pow,LL cur_m,vector<int> &idx,map<LL,LL> &ma)
  27. {
  28.   if(cur_m>m)
  29.     return;
  30.   if(pos==4)
  31.   {
  32.     if(cur_m>m)
  33.       return;
  34.     if(ma.find(cur_m)==ma.end())
  35.       ma[cur_m]=cur_pow;
  36.     else if(cur_pow > ma[cur_m])
  37.       ma[cur_m] = cur_pow;
  38.     return;
  39.   }
  40.   int i = idx[pos];
  41.   for(int j=curl[i];j<=maxl[i];j++)
  42.   {
  43.     LL mp = mus[i][j];
  44.     LL mm = sum_cost[i][j] - sum_cost[i][curl[i]];
  45.     f(pos+1,cur_pow+mp,cur_m+mm,idx,ma);
  46.   }
  47. }
  48.  
  49. LL meet_in_the_middle(map<LL,LL> m3, map<LL,LL> m4)
  50. {
  51.   LL ans = 0;
  52.   map<LL,LL> m1,m2;
  53.  
  54.   LL init = (m3.begin())->F;
  55.   LL thres = m3[init];
  56.  
  57.   m1[init] = thres;
  58.  
  59.   for(auto it:m3)
  60.   {
  61.     if(it.S>thres)
  62.     {
  63.       m1[it.F]=it.S;
  64.       thres = it.S;
  65.     }
  66.   }
  67.  
  68.   init = (m4.begin())->F;
  69.   thres = m4[init];
  70.  
  71.   m2[init] = thres;
  72.  
  73.   for(auto it:m4)
  74.   {
  75.     if(it.S>thres)
  76.     {
  77.       m2[it.F]=it.S;
  78.       thres = it.S;
  79.     }
  80.   }
  81.  
  82.  
  83.  
  84.   for(auto it:m1)
  85.   {
  86.     LL cur_m = it.F,cur_pow=it.S;
  87.     auto it2 = m2.upper_bound(m-cur_m);
  88.  
  89.     if(it2!=m2.begin())
  90.     {
  91.       it2--;
  92.       cur_pow += it2->S;
  93.       ans = max(ans,cur_pow);
  94.     }
  95.     else
  96.       assert(0);
  97.   }
  98.  
  99.   return ans;
  100. }
  101.  
  102. int main()
  103. {
  104.   int t;
  105.   icin(t);
  106.   for(int tc=1;tc<=t;tc++)
  107.   {
  108.    
  109.     lcin(m);
  110.     icin(n);
  111.  
  112.     memset(sum_cost,0,sizeof(sum_cost));
  113.    
  114.     for(int i=1;i<=n;i++)
  115.     {
  116.       icin(maxl[i]);
  117.       icin(curl[i]);
  118.       for(int j=1;j<=maxl[i];j++)
  119.         lcin(mus[i][j]);
  120.       for(int j=2;j<=maxl[i];j++)
  121.       {
  122.         lcin(cost[i][j]);
  123.         sum_cost[i][j] = sum_cost[i][j-1] + cost[i][j];
  124.       }
  125.     }
  126.     LL ans = 0;
  127.     for(int mask=1;mask<(1<<n);mask++)
  128.     {
  129.       int x = bc(mask);
  130.       if( x !=8)
  131.         continue;
  132.  
  133.       idx1.clear();
  134.       idx2.clear();
  135.       m1.clear();
  136.       m2.clear();
  137.      
  138.       for(int i=0;i<n;i++)
  139.       {
  140.         if( (mask&(1<<i)) !=0)
  141.         {
  142.           if(idx1.size()<4)
  143.             idx1.pb(i+1);
  144.           else
  145.             idx2.pb(i+1);
  146.         }
  147.       }
  148.  
  149.       f(0,0ll,0ll,idx1,m1);
  150.       f(0,0ll,0ll,idx2,m2);
  151.  
  152.       ans = max(ans,meet_in_the_middle(m1,m2));
  153.      
  154.     }
  155.     printf("Case #%d: %lld\n",tc,ans);
  156.  
  157.   }
  158. }
Add Comment
Please, Sign In to add comment