|시간 제한||메모리 제한||제출||정답||맞힌 사람||정답 비율|
|2 초||512 MB||52||39||33||71.739%|
The lectures are over, the assignments complete and even those pesky teaching assistants have nothing left to criticize about your coding project. Time to play some video games! As always, your procrastinating self has perfect timing: Cold Weather Entertainment just released Überwatch, a competitive first person video game!
Sadly, you aren’t very good at these kind of games. However, Überwatch offers more than just skill based gameplay. In Überwatch you can defeat all opponents in view with a single button press using your ultimate attack. The drawback of this attack is that it has to charge over time before it is ready to use. When it is fully charged you can use it at any time of your choosing. After its use it immediately begins to charge again.
With this knowledge you quickly decide on a strategy:
After the game your teammates congratulate you on your substantial contribution. But you wonder: How many opponents could you have defeated with optimal timing?
The game is observed over n time slices. The ultimate attack is initially not charged and requires m time slices to charge. This first possible use of the ultimate attack is therefore in the (m+1)-th time slice. If the ultimate attack is used in the i-th time slice, it immediately begins charging again and is ready to be fired in the (i + m)-th time slice.
The input consists of:
Output the maximum number of opponents you can defeat.
4 2 1 1 1 1
9 3 1 1 2 2 3 2 3 2 1