CCC '19 S4 - Tourism - DMOJ: Modern Online Judge

CCC '19 S4 - Tourism

Points: 20 (partial)

Time limit: 1.0s

Memory limit: 512M

Author:

Problem type

Canadian Computing Competition: 2019 Stage 1, Senior #4

You are planning a trip to visit $N$ ~N~ tourist attractions. The attractions are numbered from $1$ ~1~ to $N$ ~N~ and must be visited in this order. You can visit at most $K$ ~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$ ~a_i~ to attraction $i$ ~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$ ~N~ and $K$ ~K~ $(1 \le K \le N \le 10^6)$ ~(1 \le K \le N \le 10^6)~.

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

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

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

Output Specification

Output a single integer, the maximum possible total score.

Sample Input

5 3
2 5 7 1 4

Sample Output

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$ ~7 + 4 = 11~.

Comments

-4

imandrewya commented on Feb. 4, 2022, 8:14 p.m. ← edited →

Can you visit 0 attractions a day?

3

Spitfire720 commented on Feb. 4, 2022, 9:54 p.m.

Would that even matter?

3

ColonelBy_team10 commented on Feb. 13, 2022, 7:42 p.m. ← edited →

precisely. A solution with a day done nothing is equivalent to the optimal solution anyways, just as how adding 0 to a sum gives the sum anyways.

5

zhanc commented on Feb. 2, 2022, 11:22 p.m.

What's more important, a higher score or a lower amount of days? Basically if you had a situation where you could get a higher score with more days or a lower score with less days, which would be the right answer?

2

andy_zhu23 commented on Feb. 3, 2022, 3:17 a.m.

the lower amount of days. If a higher score is more important, then you should always just do N days with all elements added together, which defeats the point of this problem.

-9

maxcruickshanks commented on Oct. 10, 2021, 10:53 a.m.

Since the original data were weak, two test cases were added to the extra $15$ ~15~ marks to reward intended solutions.

This comment is hidden due to too much negative feedback. Show it anyway.

-4

d3story commented on May 8, 2021, 9:53 p.m. ← edited →

Hi, I was thinking of using F[k][j] where it will tell you the highest score you could get in k days with j breaks along the way (where each break is when you could go on further that day but you could didn't, for example, you could go 4 but you only took 1 that day so that adds 3 breaks). To update the table I was thinking of using an RMQ. The complexity of this should be O(2*(N+K)), not taking into account the RMQ, while using a little trick updating the table. Now I am stuck on the dumbest thing I can't find a way of doing an RMQ with potentially a million terms (maybe a sparse table? but I think that takes up too much space and maybe time)). SOOOO now I am just thinking my entire method is wrong, any hints? please.

2

zhenga1 commented on Feb. 9, 2021, 5:13 a.m. ← edited →

Hi, I've managed to get the first 6 points with a solution of complexity O(N*K) but I don't really see how I can get the last 9 points. Can someone help? How to O(N) it does not seem possible.

-20

ryanguorocket commented on Feb. 9, 2021, 5:58 p.m.

Try CHT.

This comment is hidden due to too much negative feedback. Show it anyway.

-9

WAO commented on Feb. 9, 2021, 11:14 p.m.

Are you trolling or what?

This comment is hidden due to too much negative feedback. Show it anyway.

30

aaronhe07 commented on July 23, 2020, 5:01 a.m.

Can an editorial be written for this problem?

19

noYou commented on July 23, 2020, 12:53 p.m.

Please

7

asdfg9240 commented on Jan. 24, 2020, 4:41 a.m.

can i get a hint for the last 9 marks?

3

ChrisLi commented on Jan. 14, 2020, 11:55 p.m.

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

0

dmojme commented on Feb. 24, 2021, 3:03 a.m.

Yes, this question is solvable using python.

1

GeeTransit commented on Feb. 20, 2021, 3:51 p.m. ← edit 2 →

So far, all Python ACs are in PyPy. No CPython ACs yet. https://dmoj.ca/problem/ccc19s4/submissions/?status=AC&language=PY2&language=PY3&language=PYPY&language=PYPY3

Edit: Yeah it's possible, but only after wasting time on it. https://dmoj.ca/submission/3436645

0

zhenga1 commented on Feb. 19, 2021, 2:58 a.m.

Use Pypy 2 or 3

32

devins commented on Feb. 26, 2019, 10:17 p.m.

cries

20

qiuxinrong27 commented on March 2, 2019, 1:13 a.m. ← edited →

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