link to the question: http://codeforces.com/contest/455/problem/A↵
↵
my submission: 75708843↵
↵
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)↵
↵
↵
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)↵
