Advertisement
Iam_Sandeep

Untitled

Aug 8th, 2022
615
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 0.81 KB | None | 0 0
  1. # cook your dish here
  2. import sys
  3. sys.setrecursionlimit(10**9)
  4. from functools import lru_cache
  5.  
  6.  
  7.  
  8. def find(a):
  9.     n=len(a)
  10.     csum=[0]*n
  11.     csum[0]=a[0]
  12.     for i in range(1,n):
  13.         csum[i]=csum[i-1]+a[i]
  14.     def psum(i,j):
  15.         return (csum[j]-csum[i]+a[i])%100
  16.     #print(cs)
  17.     @lru_cache()
  18.     def dfs(s,e):
  19.         if s>e:return 0
  20.         if s==e:return 0
  21.         ans=float('inf')
  22.         for k in range(s,e):
  23.             left=dfs(s,k)
  24.             right=dfs(k+1,e)
  25.             #print(left,right,psum(s,k),psum(k+1,e))
  26.             ans=min(ans,left+right+psum(s,k)*psum(k+1,e))
  27.  
  28.         return ans
  29.     return dfs(0,len(a)-1)
  30.  
  31.  
  32. while True:
  33.     try:
  34.         n=input()
  35.         if not n:break
  36.         a=list(map(int,input().split()))
  37.         print(find(a))
  38.     except:
  39.         break
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement