# Untitled

a guest
Jul 11th, 2016
341
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
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;
128.     {
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.       {
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. }