Problem: Time Warp
Want to try solving this problem? You can submit your code online if you log in or register.
Input File: standard input
Output File: standard output
You are a time traveller. You love concerts. Obviously, you combine these two
Your time machine is powered by units called turbo warpers. When you use
a y-year turbo warper, it propels you exactly y years into the past.
The above diagram shows the effect of using a two-year turbo warper at
the end of year 3.
It's just a jump to the left. You then continue stepping to the right like
normal. You can't use the warper again (but if you have another two-year
turbo warper on hand, you can still use that one).
Further rules on time travel:
- Your time machine is powered by lightning and dramatic clichés, so
you can only use turbo warpers at the stroke of midnight on New Year's, to
travel to previous years.
- You cannot jump back any further than the start of year 1. If using a
turbo warper would take you back further than that, it simply wouldn't work.
- Due to mild interference between your time machine and the Mayan calendar, the
world ends at the end of year X, where you are provided with the positive
integer X. You can still use turbo warpers at the very end of year X.
- You can use your turbo warpers in any order, and you don't need to use all
your turbo warpers if you don't want to.
Some years were amazing years for concert goers: who can forget the first time
Huey Lewis sang "The Power of Love"? Others were pretty terrible, like the
time The Who were gatecrashed by an overdressed fellow wearing a celery stick.
You've gone through every year in music history, and assigned it an integer
audio score - the higher the score, the better the year was.
You wish to plot a path through time, whch must start at the beginning of year
1 and finish at the end of year X, maximising the total audio score of years
you experience. Note that for each year you live through, its audio score is
added to your total regardless of how many times you have experienced that year
- The first line of input will contain one line with two space-separated
integers X and W.
- The next X lines of input will contain one integer each, the
ith of which represents the audio score of year i.
- The next W lines of input will contain one integer each, describing
the turbo warpers available to you (in no particular order).
Output should consist of a single integer: the maximum possible total audio
score you can achieve under the conditions described above.
Sample Input 1
Sample Output 1
Sample Input 2
Sample Output 2
In the first sample case, you use all your available turbo warpers for a total
audio score of:
6+9+6+9+0+8+7+8+9+0+8+7+-3 = 74
In the second sample case, you use only your 1-year turbo warpers for a total
-5 + 2 + 2 + 2 + -5 = -4
Constraints & Subtasks
The following constraints apply to all subtasks:
- 1 ≤ X ≤ 100,000, where X is the year the world ends.
- 0 ≤ W ≤ 100, where W is the number of turbo warpers you have at
- -1,000 ≤ ai ≤ 1,000, where ai is the audio score of year
- 1 ≤ bj ≤ X, where the jth turbo warper you own is a bj-year
For each subtask, the following special constraints also apply:
- For Subtask 1 (10 points), all turbo-warpers are one-year turbo-warpers (bj = 1 for all j).
- For Subtask 2 (20 points), you have exactly one turbo-warper (W = 1).
- For Subtask 3 (35 points), the world lasts no longer than one millenium (X ≤ 1000).
- For Subtask 4 (35 points), no special constraints apply.