2014 Canadian Computing Competition, Stage 2
Day 2, Problem 2: Early Exam Evacuation
You find yourself writing an exam in a long, narrow auditorium - it has N (1 ≤ N ≤ 105) rows, numbered 1..N from the front to the back, each of which has 6 seats, 3 on each side of the aisle running down the middle of the auditorium. Each seat is identified by its row number immediately followed by a letter from "A" to "F", which indicates its position in that row (with seat "A" at the far left, and "F" at the far right). The aisle lies between seats "C" and "D" in each row. The auditorium also has two secure rooms - one at the front (in front of row 1), and one at the back (behind row N).
Every seat in the auditorium is initially occupied by exactly one exam-writer per seat. However, over the course of the exam,M different exam writers decide that they have written all they can on the exam, and then would like to leave the auditorium, one after another. The i-th exam writer is in seat RiCi (1 ≤ Ri ≤ N, Ci is one of "A".."F"). When the exam writer leaves the auditorium, they must stay in one of the secure rooms until the end of the exam. Fortunately, both secure rooms can hold as many people as necessary.
Exam writers not only worry about writing exams, but they would like their lives to be as convenient as possible - as such, they're interesting in working together to minimize the total inconvenience experienced by all of them. The inconvenience a single exam-writer experiences is Ax + By, where A and B are given constants (0 ≤ A, B ≤ 109), x is the number of different people passed on the way to the chosen secure room (explained below), and y is the number of people already in that secure room before that exam-writer enters. Note that if an exam-writer does not leave their seat, their inconvenience is 0.
When walking from a seat to a secure room, one must first pass any other exam writers in the same row on the way to the aisle, and then any exam writers in seats adjacent to the aisle from that row to either row 1 or N (depending on which secure room is chosen), inclusive. Note that any vacant seats passed along the way don't count towards this value.
Can you help the poor exam writers make their lives as convenient as possible?
Input
The first line contains four space-separated integers: N (1 ≤ N ≤ 105), the number of rows in the auditorium; M (1 ≤ M ≤ 6N), the number of exam writers that leave early; A, followed by B (1 ≤ A, B ≤ 109), the constants used in determining the inconvenience caused by an exam writer leaving early.
The next M lines each contain one integer followed by one character, Ri and Ci, for i = 1..N in order, where 1 ≤ Ri ≤ N and Ci ∈ "A".."F".
You can assume that for test cases worth 60% of the marks, M ≤ 5000
Output
Output the integer which is the minimum total inconvenience experienced by all M exam writers who leave early.
Sample Input
5 5 3 4 3E 1D 5C 1E 4A
Sample Output
55
Explanation
One optimal strategy is as follows. The first person to leave can go to the front secure room, passing six people along the way (in seats 3D, 3C, 2D, 2C, 1D, and 1C) for an inconvenience of 3·6 + 4·0 = 18. The second person to leave can also go to the front secure room, passing only one person (in seat 1C) and finding one person already in the secure room, for an inconvenience of 3·1 + 4·1 = 7. The third person can go to the back secure room, passing one person for an inconvenience of 3. The fourth person can join the first two in the front secure room, passing only one person (as seat 1D is vacant at that point) for an inconvenience of 11. Finally, the fifth person to leave can go to the back secure room, passing four people and meeting one person in the back secure room for an inconvenience of 16. The total inconvenience experienced by the exam writers with this strategy is 18 + 7 + 3 + 11 + 16 = 55.
All Submissions
Best Solutions
Point Value: 25 (partial)
Time Limit: 2.00s
Memory Limit: 64M
Added: May 17, 2014
Author: SourSpinach
Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3
Comments (Search)