Description

Procat (破貓) has a lot of electrical appliances in his dormitory, such as computer, refrigerator, and electric fan. He wants to connect all the appliances to the power outlet. There is only one power outlet in his dormitory, so he needs to use extension cords and power strips to connect all the appliances to the power outlet.

Extension cords and power strips Procat currently using don't have overcurrent protection. As a friend of Procat, you are very concerned about electrical safety. You want to help Procat to connect all the appliances to the power outlet in a safe way. Luckily, you have some spare power strips with overcurrent protection. But you don't have any spare extension cords.

Power strips you have got one input and two outputs. Power strips can connect to extension cords, but power strips cannot directly connected to each other.

The price of the high-quality extension cord you want to buy is proportional to the current flowing through it. You wants to minimize the total price of the extension cords you needs to buy.

Calculate total price of the extension cords you need to connect all the appliances to the power outlet.

• After connecting all the appliances to the power outlet, it should look like a binary tree. The power outlet is the root of the tree, and the appliances are the leaves of the tree. The power strips are the internal nodes of the tree. The extension cords are the edges of the tree.

Sample

Following figures show examples of optimal ways to connect the appliances to the power outlet in each sample testcase. In each figure, squares represent power strips, circles represent appliances, and edges represent extension cords. The total price of the extension cords is the sum of current flowing through all the edges.

Sample testcase 1:

Sample testcase 2:

• Hint: Huffman Coding

Input

First line contains an integer \(N\), the number of electrical appliances Procat wants to connect to the power outlet.

The second line contains \(N\) integers \(a_1, a_2, \dots, a_N\), the power consumption of the \(N\) electrical appliances.

\(N\)
\(a_1 \quad a_2 \quad \dots \quad a_N\)

Constraints

• \(1 \leq N \leq 10^4\)
• \(1 \leq a_i \leq 10^9\)

Output

Output contains one line, the minimum total price of the extension cords Procat needs to buy. You don't need to output a newline at the end of the output.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Notice: Please use C++11 or above to submit this problem!

Notice: You may NOT use STL containers such as vector, unordered_map, unordered_set, map, set, queue, etc. Only std::string is permitted.

After reading a fantasy novel, Kuo dreams of running an adventurer's guild.

There is a guild which operates for N days this month.

There will be two kinds of events each day.

Enroll <Name> <Gold> <Power>: <Name> joins the guild with <Gold> gold and <Power> power rating. If <Name> is already in the guild today or is blacklisted, ignore this event (no fee is charged). Each time an adventurer enrolls, their gold and power are set to the values provided in that event, regardless of any previous enrollment.

Quest <Name> <Reward>: <Name> completes a quest and receives <Reward> gold from the guild. <Reward> may be positive (guild pays adventurer) or negative (adventurer pays the guild, e.g., damage fees). If <Name> is not currently in the guild or is blacklisted, ignore this event.

Whenever someone enrolls, they must pay an enrollment fee F to the guild. The fee may change every day.

Bankruptcy: If an adventurer's gold drops to 0 or below (from paying the enrollment fee or receiving a negative quest reward), they are expelled from the guild and blacklisted.

Cheating: If the quest reward exceeds twice their power rating (i.e., Reward > 2 * Power), the adventurer is suspected of fabricating difficulty — they are expelled and blacklisted. The guild still pays the reward before expelling them.

Leveling Up: After a quest, if the adventurer is not expelled and Reward >= Power, the adventurer's power increases by 1.

Blacklisted adventurers are never permitted to re-enter the guild. In particular, a blacklisted adventurer attempting to enroll will not be charged the fee.

Note: If someone must pay the enrollment fee F but only has Y gold where Y <= F, they pay all Y gold and go bankrupt. For Quest events, the reward is always applied in full — gold may go negative, after which the adventurer is expelled for bankruptcy.

At the end of each day, all adventurers leave the guild.

Input

The first line contains an integer N — the number of days the guild operates.

The following N blocks each start with Guild Q F — meaning there will be Q events and the enrollment fee is F this day.

The next Q lines are one of:

• Enroll <Name> <Gold> <Power>
• Quest <Name> <Reward>

Constraints:

• N ≤ 1000, Q ≤ 100
• At most 1000 different people across all days
• All numbers are within the range of int

Output

Print the guild's total net income on the first line — total enrollment fees collected minus total quest rewards paid out. (Note: negative rewards mean the guild collects money, so they increase income.)

If K people are blacklisted, print their names on K lines in the order they were blacklisted.

Sample Input  Download

Sample Output  Download

Partial Judge Code

14943.cpp

Partial Judge Header

14943.h

Tags

Discuss

Description

As the chief dispatcher, you are responsible for managing trains across multiple platforms. A train is essentially a sequence of train cars, each with a unique ID.

There are $M$ platforms in the station, numbered from $1$ to $M$. Initially, all platforms are empty. You will receive $Q$ operations, each belonging to one of the following five types:

• ENTER p c: A newly manufactured train car with a unique ID $c$ arrives at platform $p$. It is attached to the very end (tail) of the current train on that platform.
• MERGE p_src p_dest: The entire train on platform $p_{src}$ is moved and attached to the end of the train on platform $p_{dest}$. After this operation, platform $p_{src}$ becomes empty. If $p_{src}$ is empty before this operation, do nothing.
• REMOVE p c: Locate car $c$ currently on platform $p$ and remove it completely. The train is then reconnected, meaning the car immediately in front of $c$ (if any) and the car immediately behind $c$ (if any) are directly linked together.
• REVERSE p: Reverse the order of all cars of the train on platform $p$.
• CHECK p c k: Starting from car $c$ on platform $p$, move $k$ cars towards the front of the train. Output the ID of the car you reach. If you reach the very first car of the train before taking $k$ steps, stop and output the ID of the first car.

Hint

During peak hours, thousands of cars need to be reassigned every minute.

To prevent severe system bottlenecks, your dispatching system must be highly optimized.

Think about how to find a specific car in $O(1)$ time to perform the REMOVE and CHECK operations efficiently.

Input

The first line contains two integers $M$ and $Q$, representing the total number of platforms and the number of operations.

The following $Q$ lines each contain a command in the format described above.

It is guaranteed that:

• For ENTER, the car ID $c$ has never appeared before.
• For MERGE and SPLIT, $p_{src}$ and $p_{dest}$ are different ($p_{src} \neq p_{dest}$).
• For REMOVE and CHECK, car $c$ is guaranteed to exist currently on platform $p$.

Constraints

• $1 \le M \le 100,000$
• $1 \le Q \le 200,000$
• $1 \le p, p_{src}, p_{dest} \le M$
• $1 \le c \le 1,000,000$
• $0 \le k \le 100,000$
• The sum of the lengths of the trains reversed across all REVERSE operations will not exceed $5 \times 10^5$.

Subtasks

• Testcase 1: only ENTER and MERGE
• Testcase 2: only ENTER and REMOVE
• Testcase 3: only ENTER and REVERSE
• Testcase 4: only ENTER and CHECK
• Testcases 5-8: All operations are possible.
• Testcases 1-6: $c \le 100$.
• Testcases 7-8: No additional constraints.

Output

1. For each CHECK operation, output the resulting car ID on a new line.
2. After processing all $Q$ operations, output the final sequence of train cars on each non-empty platform.
   • For each non-empty platform from $1$ to $M$, output a line starting with the platform number, followed by a colon : and a space, and then the IDs of the cars on that platform in order from front to end, separated by a single space.
   • If a platform is completely empty, do not output anything for that platform.

Note for Sample I/O

1. ENTER 1 10: Platform 1 has [10].
2. ENTER 1 20: Platform 1 has [10, 20].
3. ENTER 2 30: Platform 2 has [30].
4. MERGE 2 1: Platform 1 has [10, 20, 30], Platform 2 is empty. (Source=2, Dest=1)
5. CHECK 1 30 1: Start at 30, move 1 step towards the front -> reaches 20. Output 20.
6. CHECK 1 30 5: Start at 30, moving 5 steps to the front exceeds the train length, so it stops at the head. Output 10.
7. REVERSE 1: Platform 1 has [30, 20, 10].
8. CHECK 1 10 2: Start at 10, move 2 steps towards the front -> reaches 30. Output 30.
9. ENTER 3 40: Platform 3 has [40].
10. REMOVE 1 20: Car 20 is removed from Platform 1. Platform 1 becomes [30, 10].
11. MERGE 1 3: Platform 3 becomes [40, 30, 10], Platform 1 is empty. (Source=1, Dest=3)

Sample Input  Download

Sample Output  Download

Partial Judge Code

14945.c

Partial Judge Header

14945.h

Tags

Discuss