### _QWOiNYUIVMPFSBKLiGSMAP_'s blog

By _QWOiNYUIVMPFSBKLiGSMAP_, history, 3 years ago,

the problem is http://codeforces.com/contest/513/problem/C

the solution is http://codeforces.com/contest/513/submission/9761274

i wonder how this solution not TLE it is 1009*1009*6*6*6 which is TLE

• -3

 » 3 years ago, # |   0 Auto comment: topic has been updated by _QWOiNYUIVMPFSBKLiGSMAP_ (previous revision, new revision, compare).
 » 3 years ago, # | ← Rev. 2 →   +5 Dude. You don't just analyze the complexity by counting for loops
•  » » 3 years ago, # ^ |   0 the each iteration in the for loop work as i clear the dp array so this is the complexity i am confused :s
•  » » » 3 years ago, # ^ |   0 For clearing the dp array, I see four for loops and they go till 6,6,6,10009 so how TLE?
•  » » » » 3 years ago, # ^ |   0 no i mean the dp is in 10009*6*6*6 okay but there is for loop iterating on dp in the main so what is the total complexity ?
•  » » » » » 3 years ago, # ^ |   +5 Memoization technique has been used in the solution, which means you just calculate the value for each state only once. Therefore the whole solution proceeds 10009*6*6*6 different states which is pretty far from TLE.
•  » » » » » » 3 years ago, # ^ |   0 i memorize on dp[i][maxi][eq][gr] for each iteration in loop maxi will be different so it is like i am doing dp again from scratch