You are given an integer N denoting the number of seats in a cinema hall numbered from 1 to N. There are M groups where B[i] denotes the number of persons in the ith group. The persons from the same group want to sit together. A[i] denotes the cost of the ith seat ticket. You have to help the cinema hall owner make the maximum possible profit by assigning the seats to the groups optimally.
Calculate the maximum profit the cinema hall owner can make through an optimal seating arrangement.
Parameters description
• N: Represents the number of seats in the cinema hall
• M: Represents the number of groups visiting the cinema hall
• A: Represents the array A, where A[i] represents the cost of the ith seat ticket
B: Represents the array B, where B[i] represents the number of persons in the ith group
Input format
The first line contains a positive integer N denoting the size of the array A. The second line contains a positive integer M denoting the size of the array B.
The third line contains N positive space-separated integers denoting elements of the array A.
The fourth line contains M positive space-separated integers denoting elements of the array B.
Output format
Print a single integer denoting the maximum profit the cinema hall owner can make through an optimal seating arrangement.
Constraints
1 <= N <= 5 * 10 ^ 2
1 <= M <= 13
1 <= A_{i} <= 10 ^ 9
1 <= B_{i} <= N
B_{1} + B_{2} + B_{3} +.......+B M <=N
You can use DP to solve this problem. I don't know if this is the best way you can do but it would work and i suppose this could be optimized further. You can make a dp[i][j] where 0<=i<=n and 0<=j<2^m. The value dp[i][j] will tell us the maximum profit we can get by filling the first i seats and j represents the subset of B which is to be used to fill first i seats.
Initialize the value of dp[i][j] to be zero for all. The value of dp[i][j] could be calculated using the following approach:
Take the maximum of dp[i-1][j] and {dp[i-b[k]][j^(1<<k)]+(sum of cost of all seats from i-b[k]+1 to i )} where 0<=k<m and kth bit of j is on(ie. ((j>>k)&1)!=0) and i>=b[k].
The sum of cost could be calculated in O(1) using prefix sums. The final answer will be dp[n][2^m-1].
This would give us a time complexity of O(n*(2^m)*m) which i think would be enough. Pardon my poor English and writing skills since it is my first comment for a solution.
Thank you!!!