CCC '19 S4 - Tourism

View as PDF

Submit solution

Points: 20 (partial)
Time limit: 1.0s
Memory limit: 512M

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
Canadian Computing Competition: 2019 Stage 1, Senior #4

You are planning a trip to visit N tourist attractions. The attractions are numbered from 1 to N and must be visited in this order. You can visit at most K attractions per day, and want to plan the trip to take the fewest number of days as possible.

Under these constraints, you want to find a schedule that has a nice balance between the attractions visited each day. To be precise, we assign a score a_i to attraction i. Given a schedule, each day is given a score equal to the maximum score of all attractions visited that day. Finally, the scores of each day are summed to give the total score of the schedule. What is the maximum possible total score of the schedule, using the fewest days possible?

Input Specification

The first line contains two space-separated integers N and K (1 \le K \le N \le 10^6).

The next line contains N space separated integers a_i (1 \le a_i \le 10^9).

For 3 of the 15 available marks, 2K \ge N.

For an additional 3 of the 15 available marks, K \le 100 and N \le 10^5.

An additional subtask worth 15 marks has been added to break solutions that are incorrect but AC on the official test data. Data provided by ChrisT.

Output Specification

Output a single integer, the maximum possible total score.

Sample Input

5 3
2 5 7 1 4

Sample Output

12

Explanation of Output for Sample Input

We need to have at least two days to visit all the attractions, since we cannot visit all attractions in one day.

Visiting the first two attractions on day 1 will give a score of 5, and visiting the last three attractions on day 2 will give a score of 7, for a total score of 12.

Visiting three attractions on day 1, and two attractions on day 2, which is the only possibility to visit in the fewest number of days possible, would yield a total score of 7 + 4 = 11.


Comments


  • 9
    aaronhe07  commented on July 23, 2020, 1:01 a.m.

    Can an editorial be written for this problem?


    • 5
      noYou  commented on July 23, 2020, 8:53 a.m.

      Please


  • 4
    asdfg9240  commented on Jan. 23, 2020, 11:41 p.m.

    can i get a hint for the last 9 marks?


    • -7
      Plasmatic  commented on Jan. 24, 2020, 3:08 p.m.

      This comment is hidden due to too much negative feedback. Click here to view it.


  • 3
    ChrisLi  commented on Jan. 14, 2020, 6:55 p.m.

    Is this question sovlable with python? I see nobody got AC for this one, similar with senior Q5.


  • 25
    devins  commented on Feb. 26, 2019, 5:17 p.m.

    cries


    • 17
      qiuxinrong27  commented on March 1, 2019, 8:13 p.m. edited

      Poor boy who decided to skip S3 and focus on S4 :( I feel you.