Avoid the bomb shot! Blue Padaengi!
Time limit1sMemory limit1024 MB
Given dog groups in a row of zones and Padaengi's start zone, decide whether Padaengi can walk within T seconds and collect exactly M dogs.
- Level
Medium5 of 10
- Topics
- Dynamic programming, Intervals, Brute force
- Solved
- No attempts yet
Problem
Padaengi studied hard in school and entered Dangdaeng University. Padaengi wanted to enjoy the joy of this success on an MT trip, but Padaengi does not drink well and is very worried.

If the others found out, they would become close without Padaengi, so Padaengi hid the fact and joined the drinking game.

The drinking game is a pairing game. zones are lined up in a row. Each dog enters the zone of its choice, and dogs in the same zone start as one group. Then each group forms a team with another group, and they must gather into groups of dogs within seconds. When a group joins another group, no member may leave it, and even before teaming up, a group cannot let any of its members leave. A dog that is not in a group of dogs within the time limit, or that breaks the rules, must drink the bomb shot as a penalty.
The other dogs stay where they are and wait for someone to take them. Padaengi fears the bomb shot and plans to lead a group of dogs personally. If Padaengi is in zone , Padaengi can move to zone or zone in 1 second, and can take or pass through the group in that zone. Taking another group costs no time, and Padaengi can still take another group at the exact moment seconds have passed since the game started.
Can Padaengi gather dogs within the time limit seconds and avoid the bomb shot?
Input
The first line contains three integers: the number of zones , the number set by the host, and the time limit in seconds, separated by spaces.
The second line contains integers , the number of dogs in each group in zones 1 through , separated by spaces.
The third line contains the integer , the zone where Padaengi's group is located at the start.
Output
Print YES if Padaengi can avoid the bomb shot, and NO otherwise.