#37893: 寫了很久才發現題目看錯了:(
s11104220@school.saihs.edu.tw
(施同學)
學校
:
臺北市立松山高級工農職業學校
編號 : 221254
來源 : [118.165.11.221]
最後登入時間 ：
2024-02-04 16:09:17
def main():
from sys import stdin
n,k=map(int,stdin.readline().split())
s=list(map(int,stdin.readline().split()))
st=[[0,n-1,1]]
#l,r,d
ans=0
#前綴績
ns=[1]*n
c=1
for i in range(n):c*=s[i];ns[i]=c
ns.insert(0,1)
#print(ns,sep="\n")
while st:
l,r,d=st.pop()
#print(l,r,"asdfadsf")
a=[]
for i in range(l+1,r):
#print(ns[i]//ns[l],ns[r+1]//ns[i+1],i)
a.append(abs(ns[i]//ns[l]-ns[r+1]//ns[i+1]))
#print(a)
ma=min(a)
#print("ma",ma)
idx=a.index(ma)+1+l
#print(s[idx])
ans+=s[idx]
if d<k:
if idx-l>=3:
st.append([l,idx-1,d+1])
if r-idx>=3:
st.append([idx+1,r,d+1])
print(ans)
if __name__=="__main__":main()
ZeroJudge Forum