DMOPC '14 Contest 8 P5 - Aurora

View as PDF

Submit solution


Points: 15 (partial)
Time limit: 0.6s
Memory limit: 256M

Author:
Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

The Aurora is an aircraft-carrying aviation submersible.


The Aurora.

N soldiers in para-mails (you can think of these as aircraft) are being deployed to one of M stations on the main continent. To travel to their respective stations, soldiers may either fly there directly with their para-mail or hitch a ride on the Aurora, which will make one journey from station 1 to station 2 to station 3 … all the way to station M. Coincidentally, this is the only route to travel between stations; that is, if a soldier wanted to travel via their own para-mail instead, they would also have to take the same route as the Aurora (because flying too far from the main route is unsafe). For each station i from 1 to M - 1, it takes exactly B seconds to travel to station i + 1 via para-mail or A seconds via the Aurora (A < B). Whenever one or more soldiers reach their station and are flying via the Aurora, the Aurora must make a stop to let all soldiers who are deployed at that station get off. The total time the Aurora stops is C \times x, where x is the number of soldiers that get off at that station. The soldiers get off one by one, so if three soldiers get off, the first soldier waits for 0 seconds, the second soldier waits for C seconds, and the last soldier waits for C \times 2 seconds. All soldiers and the Aurora will start at station 1.

The battle is beginning soon, and it is vital that each soldier arrives at their station as fast as possible. What is the minimum total time for all the soldiers to arrive at their stations?

Input Specification

The first line of input will contain N and M, separated by a single space.
The second line of input will contain A, B, and C, separated from each other by single spaces.
The third line of input will contain N integers, the assigned stations of each of the N soldiers. They will be integers from 1 to M. At least one soldier will be deployed to station M.

Constraints

Subtask 1 [30%]

1 \le N, M \le 1\,000

Subtask 2 [70%]

1 \le N, M \le 10^5

For all cases, 1 \le A, B, C \le 10^5, A < B.

Output Specification

The first and only line of output should contain the minimum total time for all the soldiers to arrive at their stations.

Sample Input 1

5 6
1 2 1
4 5 3 6 2

Sample Output 1

21

Explanation of Output for Sample Input 1

Soldier 3 and 5 should fly directly to their stations. The rest of the soldiers should use the Aurora. The total time is 3 + 5 + 4 + 7 + 2 = 21.

Sample Input 2

10 4
1 100000 1
4 3 4 2 3 2 4 3 1 4

Sample Output 2

56

Comments


  • 0
    sunnylancoder  commented on July 24, 2017, 5:52 p.m. edited

    If only one soldier gets off at say, station 1, will that cause another soldier going to station 2 to have to wait another C seconds (assuming they both take the Aurora)?

    EDIT: I'm stupid. The Aurora will stop for x*c seconds for x soldiers


  • 0
    septence123  commented on April 28, 2017, 11:28 p.m.

    Can someone please explain sample input 2 for me, I dont see how 56 is obtained


    • -3
      leonchen0613  commented on April 29, 2017, 2:43 p.m.

      Para-mail is too expensive, so all of the soldiers have to hitch a ride on the Aurora.

      The total time (from left to right) is: 3 + 3 + 5 + 4 + 6 + 6 + 9 + 9 + 0 + 11 = 56

      Note that Soldier #9 is already at the destination, so it takes 0 seconds to get there.


  • 0
    fifiman  commented on May 5, 2015, 4:54 p.m.

    Lets say a soldier 1 gets off before soldier 2. Will soldier 1's get-off Aurora time affect soldier 2's time?


    • 0
      FatalEagle  commented on May 5, 2015, 5:02 p.m.

      Assuming they both take the Aurora, yes.


  • 1
    pyrexshorts  commented on May 5, 2015, 4:38 p.m.

    If soldiers 3 and 5 go to their stations, (22 = 4 minutes for soldier 3, and 12 = 2 minutes for soldier 5), where does the other numbers come from?


    • 0
      FatalEagle  commented on May 5, 2015, 4:40 p.m.

      The other soldiers board the Aurora. Their time is calculated as described in the problem statement.


      • 0
        pyrexshorts  commented on May 5, 2015, 4:48 p.m.

        Why let the two soldiers go by themselves? Isn't it better just to take all the soldiers on the aurora? To get from 1 to 6, it is 5 minutes, and then each soldiers leaves, so 5 minutes. This would be 10 minutes no?


        • 0
          FatalEagle  commented on May 5, 2015, 5:03 p.m.

          The waiting time of soldiers increases if other soldiers get off before them.


  • 2
    kobortor  commented on May 5, 2015, 4:28 p.m.

    If soldiers 1-4 took the aurora, then why does soldier 3 take more time than soldier 1 if she is getting off at station 3 compared to 4?


    • 0
      FatalEagle  commented on May 5, 2015, 4:32 p.m.

      Sorry, soldiers 3 and 5 (in input order) should be the ones flying.


      • 0
        JeffreyZ  commented on May 5, 2015, 5:16 p.m.

        Oh, that makes sense. I just spent a long time trying to figure that out. I guess that's what I get for not refreshing the page...


  • 1
    sigkill  commented on May 5, 2015, 4:13 p.m. edited

    Is there some restriction on when/how the soldiers can fly themselves in? Reading the problem, I thought that the soldiers could all para-mail in in tandem (and independent of the Aurora), but that definitely doesn't make sense in the context of the sample input.


    • 0
      FatalEagle  commented on May 5, 2015, 4:29 p.m. edit 5

      Your thought is correct (as far as I understand it). Which part of the sample input is unclear? I'll try to explain it.

      EDIT: The explanation has been updated. I change the sample a bit, but forgot to change the explanation. Sorry!


      • 0
        sigkill  commented on May 5, 2015, 4:42 p.m.

        I'm still in the dark a little, sorry...

        If all the soldiers can just para-mail in without regard to each other or the Aurora, could they not all reach their stations within 10 units (in sample input 1)? Since B = 2, M = 6.

        I'm probably just misreading badly. :)


        • 0
          FatalEagle  commented on May 5, 2015, 4:44 p.m. edit 3

          If all soldiers use their para-mails, the total time will be

          2 \times (3 + 4 + 2 + 5 + 1) = 30 seconds.

          Note that you are asked to minimize the sum of the times instead of the maximum time.