Блог пользователя one_by_zero_

MLE DIV 3 — D , LAST DIV3 CONTEST
Автор one_by_zero_, история, 4 месяца назад, По-английски

For Problem D , why the solution is giving MLE when according to given constraint dp size is maximum 2*1e5*10 < 1e7. https://mirror.codeforces.com/contest/1992/submission/270048258

  • Проголосовать: нравится
  • +2
  • Проголосовать: не нравится

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Auto comment: topic has been updated by one_by_zero_ (previous revision, new revision, compare).

→ Ответить
»
4 месяца назад, # |
← Rev. 2   Проголосовать: нравится +6 Проголосовать: не нравится

see you have 2 states in your dp. Mainly N and K (swims in your case) both can be 2*10^5 so total in worst case is >10^9 Actually you could have taken m because m is less than 10 Anyways u dont need both k and m in and can just do in n space. Check my solution and let me know if u want me to explain

btw my dp finds min number of k needed to get past river and if thats more than k then u cant else can

→ Ответить