# HOJ 2631. Training of Lord Fish’s Fan II

### Brief description :

(N<=30, M<=1,000,000,000)

### Analyse :

/*
Author: xiaodao
Prog: HOJ 2631. Training of Lord Fish's Fan II
Status: Accepted
Last modifiy: GMT +8 Aug. 28th 10:29
*/

#include
#include
using namespace std;
const int N = 30;
map h1, h2;
int C[N], V[N]; //cost value
int n, m, step, ans;

// depth, cost, value, hash pointer..
void dfs(int k, int c, int v, map &h){
if (c>m) return;
if (k==step) h = max(h, v);
else{
dfs(k+1, c+C[k], v+V[k], h);
dfs(k+1, c, v, h);
}
}

void merge(){
map::iterator i;
map::reverse_iterator ii;

ans = max(h1.rbegin()->second, h2.rbegin()->second);

for (i=h1.begin(), ii = h2.rbegin();i!=h1.end();i++){
while (ii!=h2.rend() && i->first + ii->first > m) ii++;
if (ii==h2.rend()) return;
//printf("%u %d\n", it->first, it->second);
//printf("%u %d\n", itt->first, itt->second);
ans = max(ans, i->second + ii->second);
}
}

void solve(){
step = n/2; dfs(0, 0, 0, h1);
step = n; dfs(n/2, 0, 0, h2);

map::iterator i, ii;
for (i=h1.begin(),ii=i,ii++;ii!=h1.end();i++,ii++)
ii->second = max(i->second, ii->second);
for (i=h2.begin(),ii=i,ii++;ii!=h2.end();i++,ii++)
ii->second = max(i->second, ii->second);
merge();
}

void init(){
scanf("%d %d", &n, &m);

int x, y;
for (int i=0;i> T;
while (T--){
init(); solve();
cout << ans << endl;
}
}