link to the question: http://mirror.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)
The code has two nested loops, which makes it O(n^2). In the editorial, you can find a faster O(n) solution.
In general, if you can find something in the editorial, do not waste people's time asking for it on the blog.
How to add the submission link? Go to your profile. Choose the tab "Submissions". Right click on your submission number and copy link. So this is the link: https://mirror.codeforces.com/contest/455/submission/75710100
You may have noticed a few downvotes under the post. Please take care of how you write. OVERUSING BIG LETTERS make you seem SHOUTING. Use commas (,) and dots (.) in a right way so that your post looks tidy and people want to read it.
Well, mate; I will keep that in mind from now onwards; it was my first blog so didn't have much experience.
That is fine. Good luck in problem solving and future contests :)