one_by_zero_'s blog

MLE DIV 3 — D , LAST DIV3 CONTEST
By one_by_zero_, history, 5 months ago, In English

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

  • Vote: I like it
  • +2
  • Vote: I do not like it

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
5 months ago, # |
← Rev. 2   Vote: I like it +6 Vote: I do not like it

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

→ Reply