This is the problem[This is the problem](http://Vasya and Good Sequences)Can someone explain me why it is so written in its tutorial that if the length of sequence is greater than 61 than we don't need to check the maximum condition![problem:1030E]
→ Обратите внимание
До соревнования
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
11:21:11
Зарегистрироваться »
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
11:21:11
Зарегистрироваться »
*есть доп. регистрация
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3823 |
| 3 | Benq | 3738 |
| 4 | Radewoosh | 3633 |
| 5 | jqdai0815 | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | ksun48 | 3390 |
| 10 | gamegame | 3386 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | Um_nik | 163 |
| 3 | maomao90 | 162 |
| 4 | atcoder_official | 161 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 157 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 9 | nor | 153 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 23.11.2024 06:13:50 (l2).
Десктопная версия, переключиться на мобильную.
При поддержке
Atleast provide the link to the question.
$$$a_i > 0$$$, so every number has at least 1 bit set. So over a segment of length 61 or more, we are guaranteed to have a sum $$$S \geq 61$$$. Since the maximum value for $$$b_i$$$ is 61, we can be sure that this segment has $$$S \geq b_i$$$.
Do comment back if you didn't understand something :)
Ok, so it means that even in the worst case in a segment with more than 61 elements where only one element is 61 and all the rest 61 are 1,I will have my sum equal to or greater than 61 excluding the max (61). Thanks, for explaining!
This is the accepted code, for your reference :)
poor Vasya