Problem p03299 (python)

Fixed submission:
mod=10**9+7
n=int(input())
H=list(map(int,input().split()))

def solve(h):
    if not h:
        return 1
    elif len(h)==1:
        return pow(2,h[0],mod)
    N=len(h)
    a=[h[i] for i in range(N)]
    a=list(set(a))
    a.sort()
    comp={i:e+1 for e,i in enumerate(a)}
    data={comp[e]:e for e in comp.keys()}
    data[0]=0
    data[0]=1
    #print(comp)

    dp=[[0 for i in range(len(a)+1)] for j in range(N)]

    i=0
    if h[i+1]>=h[i]:
        id=comp[h[i]]
        id2=comp[h[i+1]]
        for j in range(id,id2+1):
            dp[i][j]=2
        for j in range(0,id):
            dp[i][j]=1
    else:
        id=comp[h[i+1]]
        for j in range(0,id):
            dp[i][j]=pow(2,h[i]-h[i+1],mod)
        dp[i][id]=2*(pow(2,h[i]-h[i+1],mod)-1)
        dp[i][id]%=mod
        id2=comp[h[i]]
        dp[i][id]+=2
        dp[i][id]%=mod

    for i in range(1,N-1):
        if h[i+1]>=h[i]:
            id=comp[h[i]]
            id2=comp[h[i+1]]
            for j in range(id,id2+1):
                dp[i][j]=(2*dp[i-1][id])%mod
            for j in range(0,id):
                dp[i][j]=dp[i-1][j]
        else:
            id=comp[h[i+1]]
            id2=comp[h[i]]
            for j in range(0,id):
                dp[i][j]=(pow(2,h[i]-h[i+1],mod)*dp[i-1][j])%mod
            for j in range(id,id2):
                low=data[j]
                up=data[j+1]-1
                dp[i][id]+=dp[i-1][j]*pow(2,h[i]-up,mod)*(pow(2,up-low+1,mod)-1)
            dp[i][id]%=mod
            dp[i][id]+=2*dp[i-1][id2]
            dp[i][id]%=mod

    ans=0
    id=comp[h[-1]]
    for i in range(0,id):
        low=data[i]
        up=data[i+1]-1
        ans+=dp[N-2][i]*pow(2,h[-1]-up,mod)*(pow(2,up-low+1,mod)-1)
        ans%=mod
    ans+=2*dp[N-2][id]
    ans%=mod
    return ans

ans=pow(2,H.count(1),mod)
check=[i for i in range(n) if H[i]==1]
check=[-1]+check+[n]
for i in range(len(check)-1):
    l,r=check[i],check[i+1]
    ans*=solve(H[l+1:r])
    ans%=mod

print(ans)

Buggy submission (verdict: Runtime Error):
mod=10**9+7
n=int(input())
H=list(map(int,input().split()))

def solve(h):
    if not h:
        return 1
    elif len(h)==1:
        return pow(2,h[0],mod)
    N=len(h)
    a=[h[i] for i in range(N)]
    a=list(set(a))
    a.sort()
    comp={i:e+1 for e,i in enumerate(a)}
    data={comp[e]:e for e in comp.keys()}
    data[0]=0
    data[0]=1
    #print(comp)

    dp=[[0 for i in range(len(a)+1)] for j in range(N)]

    i=0
    if h[i+1]>=h[i]:
        id=comp[h[i]]
        dp[i][id]=2
        dp[i][id+1]=2
        for j in range(0,id):
            dp[i][j]=1
    else:
        id=comp[h[i+1]]
        for j in range(0,id):
            dp[i][j]=pow(2,h[i]-h[i+1],mod)
        dp[i][id]=2*(pow(2,h[i]-h[i+1],mod)-1)
        dp[i][id]%=mod
        id2=comp[h[i]]
        dp[i][id]+=2
        dp[i][id]%=mod

    for i in range(1,N-1):
        if h[i+1]>=h[i]:
            id=comp[h[i]]
            id2=comp[h[i+1]]
            for j in range(id,id2+1):
                dp[i][j]=(2*dp[i-1][id])%mod
            for j in range(0,id):
                dp[i][j]=dp[i-1][j]
        else:
            id=comp[h[i+1]]
            id2=comp[h[i]]
            for j in range(0,id):
                dp[i][j]=(pow(2,h[i]-h[i+1],mod)*dp[i-1][j])%mod
            for j in range(id,id2):
                low=data[j]
                up=data[j+1]-1
                dp[i][id]+=dp[i-1][j]*pow(2,h[i]-up,mod)*(pow(2,up-low+1,mod)-1)
            dp[i][id]%=mod
            dp[i][id]+=2*dp[i-1][id2]
            dp[i][id]%=mod

    ans=0
    id=comp[h[-1]]
    for i in range(0,id):
        low=data[i]
        up=data[i+1]-1
        ans+=dp[N-2][i]*pow(2,h[-1]-up,mod)*(pow(2,up-low+1,mod)-1)
        ans%=mod
    ans+=2*dp[N-2][id]
    ans%=mod
    return ans

ans=pow(2,H.count(1),mod)
check=[i for i in range(n) if H[i]==1]
check=[-1]+check+[n]
for i in range(len(check)-1):
    l,r=check[i],check[i+1]
    ans*=solve(H[l+1:r])
    ans%=mod

print(ans)