Сегодня в 21:00 мск состоится SRM 535. После матча тут по традиции можно обсудить задачи.
→ Обратите внимание
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3792 |
| 2 | VivaciousAubergine | 3647 |
| 3 | Kevin114514 | 3611 |
| 4 | jiangly | 3583 |
| 5 | strapple | 3515 |
| 6 | tourist | 3470 |
| 7 | Radewoosh | 3415 |
| 8 | Um_nik | 3376 |
| 9 | maroonrk | 3361 |
| 10 | XVIII | 3345 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 162 |
| 2 | adamant | 148 |
| 3 | Um_nik | 146 |
| 4 | Dominater069 | 143 |
| 5 | errorgorn | 141 |
| 6 | cry | 138 |
| 7 | Proof_by_QED | 136 |
| 8 | YuukiS | 135 |
| 9 | chromate00 | 134 |
| 10 | soullless | 133 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2026 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 21.05.2026 13:16:58 (g1).
Десктопная версия, переключиться на мобильную.
При поддержке
Как решать вторую(div 1)/почему капитанское решение неверно?
Потому что надо отучиваться от привычки писать первое что не можешь сходу опровергнуть.
Решение. Пусть ответ ≤ А·totalWork.
Тогда
Тогда 
.
Ну а здесь уже жадность брать K максимальных по ai·(A - pi), очевидно работает.
Сделали бинпоиск по А.
Если я правильно понимаю что такое капитанское, то оно валится тестом n=3, k=2, totalwork=2, a={1,90000,1}, p={1,90000,100000}, ответ — 107201 (надо отработать 1 и 3-ему, хотя на первый взгляд 3-ий хуже 2-ого).
500 Div 1: жадность заходит, или нет?
У меня почелленджили
Зависит от того, что называть жадностью. Самая тупая не проходит (у меня тоже почелленджили).
Соль в том, что жадная оценочная функция вроде бы неверная — из-за приписки о том, что все должны работать поровну в плане времени.
Такая же, что описал PavelKunyavskiy выше.
Судя по рейтингу постов выше, в тему начали заходить люди, которых, после фэйла их 500, злит любое упоминание о ней.
Похожая на 1000 была на зимней школе в Харькове. Те, кто ее сдали, писали решение за O(S * S * W)?
Ого, на какую? Я что-то не могу вспомнить.
Ну там на коротком контесте Антона Лунева была задача, где динамика пересчитывалась примерно как
f(x) = k * f(x - 1) + (k - 1) * f(x - 2) + ... + f(x - k + 1). Здесь вроде бы не тяжелая динамика за O(S3W), в которой примерно такой же переход, который так же оптимайзится до O(S2W).И я. А то что мы оба не можем вспомнить уже на правду не очень похоже.
Я умею решать за O(S4 + WH), но не успел написать.
Помимо того, что я не придумал правильное решение в 500, я еще и затупил в харде — зачем то степени S брал вместо S + 1. В итоге вместо ~5го места сейчас окажусь в конце второй сотни
Как решать 1000?
Ну, есть очевидная динамика с O(SWH) состояний и O(S2WH) операций. Так как переходов вниз не более S, то она превращается в O(S2W) состояний и O(S3W) операций. А дальше надо пересчет сделать за O(1), для этого надо предподсчитывать суммы вида ans[i][j][k] + 2 * ans[i][j][k-1] + 3 * ans[i][j][k-2] + ...
Я умею оптимизировать очевидную динамику до O(S^2*(W+H)), пользуясь тем что матрицы перехода вниз и вправо коммутируют. Failed systests из-за неразобранного случая 1x1 :(
автор с ником wrong — мечта троллей)