TLE '16 Contest 6 (Mock CCC) J4 - Ski Rentals

Points: 7 (partial)

Time limit: 1.0s

Memory limit: 256M

Author:

Problem type

You are waiting in line to obtain ski rentals at Hack the North 2017. To get your ski, you must wait in one of three lines. Each line will have $S$ ~S~, $K$ ~K~, and $I$ ~I~ skiers respectively. Additionally, each skier will have a wait time $W$ ~W~ attached to them, where $W$ ~W~ represents the number of seconds it takes for them to choose a rental.

At the end of every $30$ ~30~ seconds, the last skier from the longest line (not longest wait time) will move to a line with a fewer amount of people if that line consists of fewer people than the one they are currently waiting in. If there are ties for the shortest or longest lines, nobody will move. The skiers who move will switch regardless of the new wait time in front of them.

How long will it take for all skiers to get their rentals?

Input Specification

The first line of input consists of three integers separated by spaces: $S$ ~S~, $K$ ~K~, and $I$ ~I~ $(1 \le S,K,I \le 100\,000)$ ~(1 \le S,K,I \le 100\,000)~.

The second line of input will have the wait times for the $S$ ~S~ skiers in the $1^\text{st}$ ~1^\text{st}~ line, in order from front to end of the line.

The third line of input will have the wait times for the $K$ ~K~ skiers in the $2^\text{nd}$ ~2^\text{nd}~ line, in order from front to end of the line.

The fourth line of input will have the wait times for the $I$ ~I~ skiers in the $3^\text{rd}$ ~3^\text{rd}~ line, in order from front to end of the line.

It is guaranteed that $0 \le W \le 5000$ ~0 \le W \le 5000~.

For 4 of the 15 available marks, $S,K,I \le 100$ ~S,K,I \le 100~ and $W \le 50$ ~W \le 50~.
For an additional 4 of the 15 available marks, $S,K,I \le 10\,000$ ~S,K,I \le 10\,000~ and $W \le 500$ ~W \le 500~.
For an additional 4 of the 15 available marks, $W \le 5000$ ~W \le 5000~.

Output Specification

The output will contain a single integer, the number of seconds it takes for all skiers to get their rentals.

Sample Input 1

Sample Output 1

Sample Input 2

Sample Output 2

Comments

0

minecraftyugi commented on Feb. 21, 2017, 3:31 a.m.

If there isn't a tie for the shortest or longest line, does the skier at the back of the longest line move to the back of the shortest line or the back of the second-shortest line, or the back any of those two lines?

-1

nathanl3 commented on Feb. 21, 2017, 4:10 a.m.

The skier will move to the back of the shortest line (the one with the least amount of people).