Slastičarnica
레이팅 미적용의견: 0
There \(is\) \(a\) new bakery \(in\) town! Come and try delicious cakes from Dodo’s bakery!
The bakers have prepared \(n\) cakes, the \(i-th\) of which has sweetness \(a@@RISE_MATH_BLOCK_0@@i\) cakes whose sweetnesses are at least \(s\)\(i\)”.
Dorijan serves customers in a peculiar way. He will give \(d_{i}\) continuous cakes from
the table. To keep the table looking as nice as possible he will only give cakes from
the left or the right edge of the table. He noticed that he cannot serve a lot of customers that way, so
before serving a customer he will eat some cakes (possibly none) from the edges of the table.
If Dorijan cannot satisfy a customer, he will close the bakery for the day. What is the largest number of
customers he can serve, before closing?
Subtask 1 (21 points): n, \(q \le 100\)
Subtask 2 (31 points): \(d@@RISE_MATH_BLOCK_0@@q = 1\)
Subtask 3 (58 points): No additional constraints.
The first line contains two integers n, q (\(1 \le n \le 5\,000\), \(1 \le q \le 2 \cdot 10^{5}\)), the number of cakes and the
number of people in the line.
The second line contains \(n\) numbers \(a_{i}\) (\(1 \le a_{i} \le 10^{9}\)), where \(a_{i}\) is the sweetness of the \(i-th\) cake.
In each of the next \(q\) lines there are two integers \(d@@RISE_MATH_BLOCK_0@@i\) (\(1 \le d@@RISE_MATH_BLOCK_1@@i \le 10^{9}\)), the order of the \(i-th\)
customer in line.
In the first and only line output the number of customers Dorijan can serve.
| 서브태스크 | 점수 | 설명 |
|---|---|---|
1 | 21점 | n, \(q \le 100\) |
2 | 31점 | \(d@@RISE_MATH_BLOCK_0@@q = 1\) |
3 | 58점 | No additional constraints. |
5 6
1 2 3 4 5
1 1
1 2
1 3
1 4
1 6
1 545 3
1 3 2 2 1
3 1
1 3
2 229 5
1 3 2 5 1 4 6 2 1
3 2
2 3
1 1
1 2
1 14Clarification of the third example:
Dorijan first eats one cake from the left, then gives the next three cakes with sweetnesses 3, 2, and 5 to
the first customer. He then eats another cake from the left and gives the next two cakes with sweetnesses
4 and 6 to the second customer. The third customer gets a cake from the right with sweetness 1 and the
fourth gets the last cake with sweetness 2. Dorijan unfortunately does not have more cakes, so the last
customer goes home empty-handed.
평가 및 의견
Slastičarnica
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Slastičarnica