この問題は個目の荷物の重さが,価値がであり,許容重量がである ナップサック問題に帰着できます.
時間計算量はで,この問題の制約下では十分高速です.
def make_vec(*dims, initial=0):
n = len(dims)
code = "[" * n + "{}] * {}" + " for _ in range({})]" * (n - 1)
return eval(code.format(initial, *reversed(dims)))
def div(n):
res=[]
i=int(1)
while i*i<=n:
if n%i==0:
res.append(i)
if n!=i**2:
res.append(n//i)
i+=1
res.sort()
return res
n=int(input())
A=[]
for x in range(1,n+1):
A.append(len(div(x)))
dp=make_vec(n+1,n+1)
for i in range(1,n+1):
for j in range(n+1):
if dp[i-1][j]==0 and j!=0:
continue
dp[i][j]=max(dp[i][j],dp[i-1][j])
if i+j<=n:
dp[i][j+i]=max(dp[i][j+i],dp[i-1][j]+A[i-1])
print(dp[n][n])
解説とは関係ないですが「正整数を正の奇数の和に分解する場合の数」と 「正整数を相異なる正整数の和に分解する場合の数」は一致するらしいです.