TIME LIMIT EXCEEDED IN 455A BOREDOM

Revision en2, by jha_saurav, 2020-04-07 06:53:40

link to the question: http://codeforces.com/contest/455/problem/A

The code has been written in python and dynamically programmed. But, i am getting TLE on test case 11. Please ,help in optimising the code if possible and if not; please tell why the code is getting TLE; is it because of python being a slower language or there is some issue in code?? PLEASE, HELP OUT!!

SOURCE CODE:(I DO NOT KNOW HOW TO SHARE SUBMISSION LINK!!):

def boredom(freq_li,i,n): dp=[-1 for i in range(n+1)] dp[n-1]=(n-1)*freq_li[n-1],(n-1)*freq_li[n-1] dp[n]=0,0

for k in range(n-2,-1,-1):
    if freq_li[k]==0:
        dp[k]=dp[k+1]        
    else:
        inclusive_k=k*freq_li[k]
        for j in range(k+2,n):
            curr_ans=dp[j]
            ans=k*freq_li[k]+curr_ans[0]
            inclusive_k=max(inclusive_k,ans)    

        ans=dp[k+1]
        exclusive_k=ans[1]

        overall=max(inclusive_k,exclusive_k)
    dp[k]=inclusive_k,overall    

return dp[0]

n=int(input()) li=[int(x) for x in input().split()] maxm=max(li) freq_li=[0 for i in range(maxm+1)] for ele in li: freq_li[ele]+=1

max_points=boredom(freq_li,0,maxm+1)[1] print(max_points)

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English jha_saurav 2020-04-07 06:53:40 953
en1 English jha_saurav 2020-04-07 06:52:12 437 Initial revision (published)