There are n rooms (numbered 0 to n-1).
Room i contains Ci bottles, each with some volume.
Little Elephant visits rooms in a sequence given by array P of length m:
First visit → room P[0]
Second visit → room P[1]
…
m-th visit → room P[m-1]
Rule when visiting a room:
He looks at all bottles currently present in that room, finds the one with maximum volume, drinks it completely (i.e., removes that bottle).
If the room is visited again later, he again drinks the largest remaining bottle in that room (if any).
Your task: For each test case, compute the total volume of lemonade he drinks over all visits.
Input Format:
First line: integer T — number of test cases.
For each test case:
First line: two integers n and m
n — number of rooms
m — number of visits
Second line: m integers — array P (room indices visited).
Next n lines — description of bottles in each room:
For room i, the line format is:
Ci V0 V1 ... V(Ci-1)
Ci = count of bottles in room i
Vj = volume of j-th bottle
Output Format:
For each test case, print a single integer: total volume drunk.
Constraints:
1 ≤ T ≤ 10
1 ≤ n,Ci ≤ 100
1 ≤ m ≤ 104
0 ≤ Pi < n
1 ≤ Vi ≤ 105
Max visits per test: 104
Max rooms: 100
Max bottles per room: 100
Sample:
Input:
2
3 3
0 2 1
3 1 2 3
1 7
2 4 7
4 7
0 1 3 0 1 0 0
1 7
3 9 4 5
7 1 2 3 4 5 6 7
1 1
17
22
Output:
17
22
You can verify by simulating the described behavior.
Intuition
We need to simulate:
For each visit to room r, pick the current maximum bottle in that room and remove it.
This is a classic scenario for using a max-heap (priority queue):
For each room, we want to efficiently get and remove the maximum volume repeatedly.
Given constraints:
Each room has at most 100 bottles.
Each test can have at most 10,000 visits.
n ≤ 100 rooms.
A priority queue per room (max-heap) will work efficiently:
Each extraction O(log Ci) where Ci ≤ 100 → effectively cheap.
Approach
Data Structure Choice:
For each room i:
Store volumes in a max-heap:
In C++: priority_queue<int>
In Java: PriorityQueue<Integer> with reversed comparator (max-heap)
In Python: use heapq as min-heap with negative values or sort and maintain index
In JavaScript/C: we can simulate heap or use simple sorting + pointer since Ci ≤ 100
Simplest & efficient:
Since each room has at most 100 bottles, we can:
Sort each room’s volumes in descending order.
Maintain an index pointer for each room to the “next largest unused” bottle.
On each visit, if pointer is still within the list, take that value and increment pointer.
This avoids implementing heaps and is O(CilogCi) for sorting each room, then O(1) per extraction.
Total per test case:
Building: sum over rooms ≤n*100*log100 → small
Visits: m≤104 with just index increments → fast.
Algorithm (Using Sorting per Room):
For each test case:
Read n, m.
Read array P of length m.
For each room i in 0..n-1:
Read Ci, along with Ci volumes.
Store volumes in a vector/list.
Sort this list in descending order.
Create an array pos of size n, initialized with 0:
pos[i] = index of the next available bottle in room i’s sorted list.
Initialize total = 0.
For each visit index k from 0 to m-1:
Let room = P[k].
If pos[room] is less than the length of that room’s list:
Take volume v = rooms[room][pos[room]].
Add v to total.
Increment pos[room] by 1.
Else:
Room has no bottles left → Elephant drinks nothing from this room.
After processing all visits, print total.
Edge Cases:
Room visited more times than it has bottles:
After all bottles are consumed, further visits contribute 0.
Some rooms may have 0 bottles?
According to constraints Ci >= 1, but even if 0, our logic (empty list) is safe: pos[i] is 0, size is 0 → no drinks.
Large volumes (up to 10^5) → use 64-bit type (long long in C/C++, long in Java, Python int is arbitrary precision).
Pseudo code:
C++ code
Python code
JavaScript code
Comments
Post a Comment