307229: CF1324E. Sleeping Schedule
Memory Limit:256 MB
Time Limit:2 S
Judge Style:Text Compare
Creator:
Submit:15
Solved:0
Description
Sleeping Schedule
题意翻译
+ 题目描述 Vova有个非常奇怪的睡眠日程表。一天有$h$个小时,Vova将正好睡$n$次觉,从每次刚醒来的那一刻计起,他将在$a_i$小时后睡第$i$次觉。你可以假设Vova在故事开始时是刚醒来的。(初始时间为0)每次Vova正好睡一天(也就是$h$小时)。 如果他在$[l,r]$时间段内开始睡觉,便认为这一次睡眠是优秀的。 Vova可以控制自己,在第$i$次睡眠前,选择在$a_i$或$a_i-1$小时后开始睡觉。 你的任务是计算出优秀睡眠次数的最大值。 + 输入格式 第一行$n,h,l,r$ $(1 \le n \le 2000,3 \le h \le 2000,0 \le l \le r < h)$ 第二行$n$个整数,分别表示$a_i$ $(1 \le a_i < h)$ + 输出格式 一个整数,优秀睡眠的最大值。题目描述
Vova had a pretty weird sleeping schedule. There are $ h $ hours in a day. Vova will sleep exactly $ n $ times. The $ i $ -th time he will sleep exactly after $ a_i $ hours from the time he woke up. You can assume that Vova woke up exactly at the beginning of this story (the initial time is $ 0 $ ). Each time Vova sleeps exactly one day (in other words, $ h $ hours). Vova thinks that the $ i $ -th sleeping time is good if he starts to sleep between hours $ l $ and $ r $ inclusive. Vova can control himself and before the $ i $ -th time can choose between two options: go to sleep after $ a_i $ hours or after $ a_i - 1 $ hours. Your task is to say the maximum number of good sleeping times Vova can obtain if he acts optimally.输入输出格式
输入格式
The first line of the input contains four integers $ n, h, l $ and $ r $ ( $ 1 \le n \le 2000, 3 \le h \le 2000, 0 \le l \le r < h $ ) — the number of times Vova goes to sleep, the number of hours in a day and the segment of the good sleeping time. The second line of the input contains $ n $ integers $ a_1, a_2, \dots, a_n $ ( $ 1 \le a_i < h $ ), where $ a_i $ is the number of hours after which Vova goes to sleep the $ i $ -th time.
输出格式
Print one integer — the maximum number of good sleeping times Vova can obtain if he acts optimally.
输入输出样例
输入样例 #1
7 24 21 23
16 17 14 20 20 11 22
输出样例 #1
3