Problem: Time Limit: 8 sec / Memory Limit: 64 MB





Example

Input

3 3 2
1 1
2 1 1
3 1 1 1


Output

8

Solution (in CPP):

Solution:
#include <stdio.h>
#include <cmath>
#include <math.h>
#include <algorithm>
#include <cfloat>
#include <stack>
#include <queue>
#include <vector>
#include <string>
#include <iostream>
#include <set>
#include <map>
#include <time.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;


struct Info{
	Info(){
		loc = weight = 0;
	}
	Info(int arg_loc,int arg_weight){
		loc = arg_loc;
		weight = arg_weight;
	}
	int loc,weight;
};

struct Data{
	Data(int arg_state,int arg_total_cost){
		state = arg_state;
		total_cost = arg_total_cost;
	}
	bool operator<(const struct Data &arg) const{
		return total_cost > arg.total_cost;
	}
	int state,total_cost;
};


int main(){

	int POW[16];
	for(int i = 0; i < 16; i++)POW[i] = pow(2,i);

	int N,init_pos,W;
	scanf("%d %d %d",&N,&init_pos,&W);

	vector<int> V[N+1];
	Info info[15];
	int index = 0,tmp,max_h;

	for(int h = 1; h <= N; h++){
		scanf("%d",&tmp);
		for(int i = 0; i < tmp; i++){
			scanf("%d",&info[index].weight);
			if(h == 1)continue;
			max_h = h;
			info[index].loc = h;
			V[h].push_back(index);
			index++;
		}
	}

	if(index == 0){
		printf("0\n");
		return 0;
	}

	int* min_cost = new int[POW[index]];
	int pre_cost,ans = abs(init_pos-max_h),state = 0,item_num = 0,item_id[index],sum_weight;
	int rest_num,rest_id[index],add_state,not_carry_min_weight,add_cost;
	priority_queue<Data> Q;

	for(int floor = max_h; floor >= 2; floor--){

		if(V[floor].size() == 0){
			ans += pre_cost;
			continue;
		}
		for(int i = 0; i < V[floor].size(); i++){
			item_id[item_num++] = V[floor][i];
		}
		state = POW[item_num];

		for(int i = 0; i < state; i++)min_cost[i] = BIG_NUM;

		Q.push(Data(0,0));

		while(!Q.empty()){

			if(Q.top().state == state-1){
				Q.pop();
			}else if(Q.top().total_cost > min_cost[Q.top().state]){
				Q.pop();
			}else{

				rest_num = 0;
				for(int loop = 0; loop < item_num; loop++){
					if(Q.top().state & (1 << loop)){
						//do nothing
					}else{
						rest_id[rest_num++] = loop;
					}
				}

				for(int state = 1; state < POW[rest_num]; state++){
					sum_weight = 0;
					not_carry_min_weight = BIG_NUM;
					add_state = 0;
					for(int loop = 0; loop < rest_num; loop++){
						if(state & (1 << loop)){
							sum_weight += info[item_id[rest_id[loop]]].weight;
							add_state += POW[rest_id[loop]];
						}else{
							not_carry_min_weight = min(not_carry_min_weight,info[item_id[rest_id[loop]]].weight);
						}
					}

					if(sum_weight > W || sum_weight+not_carry_min_weight <= W)continue;

					if(Q.top().state == 0){
						add_cost = 1;
					}else{
						add_cost = 2;
					}

					if(min_cost[Q.top().state+add_state] > Q.top().total_cost+add_cost){
						min_cost[Q.top().state+add_state] = Q.top().total_cost+add_cost;
						Q.push(Data(Q.top().state+add_state,min_cost[Q.top().state+add_state]));
					}
				}
				Q.pop();
			}
		}
		ans += min_cost[state-1];
		pre_cost = min_cost[state-1];
	}

	printf("%d\n",ans);

	return 0;
}