№ | Пользователь | Рейтинг |
---|---|---|
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 | 166 |
2 | maomao90 | 163 |
2 | Um_nik | 163 |
4 | atcoder_official | 161 |
5 | adamant | 159 |
6 | -is-this-fft- | 158 |
7 | awoo | 157 |
8 | TheScrasse | 154 |
9 | nor | 153 |
9 | Dominater069 | 153 |
Название |
---|
Нам дан правильный, выпуклый многоугольник, где никакие три вершины не лежат на одной прямой на любой прямой лежат максим две вершины многоугольника, а хорда - часть прямой, где концы это наши ровно две вершины.
И вообще, хорда в окружности соединяет ровно две точки с окружности!
3 хорды — 3 * 2 = 6 вершин.
1) разделим на блоки, которые будут ограничиваться 0.
пока не встретятся k отрицательных чиселточнее пока не встретим k+1ое отрицательное число, его не обработаем. Аналогично с суффиксом. Запомним максимумМожно считать не A1*A2*A3*A4...*An - это надо будет хранить в длинном числе и считать долго, а считать ln(A1)+ln(A2)+ln(A3)+ln(A4)...+ln(An) - это можно хранить в дабле и считать за O(R-L+1). ln тут - это натуральный, логарифм, например. И сравнивать тогда надо не длинные числа а даблы. Это правильно потому, что A*B = exp(ln(A)+ln(B)), где exp(x) - е в степени x(совсем не умею пользоваться LaTeX'ом).
upd: мой код
mincost-maxflow. Можно разбить поле на группы по 4 клетки, получающиеся поворотами друг из друга. Вершины сети - буквы и группы. Стоимости и пропускные способности считаются несложно. Как-то так.