Problem:


Score : 1100 points

Problem Statement

Let us consider a grid of squares with 10^9 rows and N columns. Let (i, j) be the square at the i-th column (1 \leq i \leq N) from the left and j-th row (1 \leq j \leq 10^9) from the bottom.

Snuke has cut out some part of the grid so that, for each i = 1, 2, ..., N, the bottom-most h_i squares are remaining in the i-th column from the left.
Now, he will paint the remaining squares in red and blue.
Find the number of the ways to paint the squares so that the following condition is satisfied:

Every remaining square is painted either red or blue.

For all 1 \leq i \leq N-1 and 1 \leq j \leq min(h_i, h_{i+1})-1, there are exactly two squares painted red and two squares painted blue among the following four squares: (i, j), (i, j+1), (i+1, j) and (i+1, j+1).

Since the number of ways can be extremely large, print the count modulo 10^9+7.

Constraints

1 \leq N \leq 100

1 \leq h_i \leq 10^9

Input

Input is given from Standard Input in the following format:

N
h_1 h_2 ... h_N

Output

Print the number of the ways to paint the squares, modulo 10^9+7.

Sample Input 1

9
2 3 5 4 1 2 4 2 1

Sample Output 1

12800

One of the ways to paint the squares is shown below:

  #
  ##  #
 ###  #
#### ###
#########

Sample Input 2

2
2 2

Sample Output 2

6

There are six ways to paint the squares, as follows:

## ## ## ## ## ##
## ## ## ## ## ##

Sample Input 3

5
2 1 2 1 2

Sample Output 3

256

Every way to paint the squares satisfies the condition.

Sample Input 4

9
27 18 28 18 28 45 90 45 23

Sample Output 4

844733013

Remember to print the number of ways modulo 10^9 + 7.



Sample input:
9
2 3 5 4 1 2 4 2 1


Sample output:
12800

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7

n = I()
H = LI()
dp = [2] * n
ret = pow(2, H[0], mod)
for kk in range(n):
    if H[0] > H[kk]:
        dp[kk] = pow(2, H[0] - H[kk], mod)
    else:
        dp[kk] = 2


for k in range(1, n):
    for i in range(n):
        if H[i] < H[k]:
            dp[i] = dp[i] * 2 * pow(2, H[k] - H[i] - 1, mod) % mod
        else:
            dp[i] = dp[i] * 2 % mod
    if H[k] == 1:
        ret = ret * 2 % mod
    elif H[k] > H[k - 1]:
        ret = dp[k] * 2 + (ret - dp[k]) * pow(2, H[k] - H[k - 1], mod)
    else:
        ret = dp[k] * 2 + (ret - dp[k])
    ret %= mod



print(ret)
# print(acc)
# print(c)
# 40, 96 , 4

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7

n = I()
H = LI()
dp = [2] * n
ret = pow(2, H[0], mod)
for kk in range(n):
    if H[0] > H[kk]:
        dp[kk] = pow(2, H[0] - H[kk], mod)
    else:
        dp[kk] = 2


for k in range(1, n):
    for i in range(n):
        if H[i] < H[k]:
            dp[i] = dp[i] * 2 * pow(2, H[k] - H[i] - 1, mod) % mod
        else:
            dp[i] = dp[i] * 2 % mod
    if H[k] == 1:
        ret = ret * 2 % mod
    elif H[k] > H[k - 1]:
        ret = dp[k] * 2 + (ret - dp[k]) * pow(2, H[k] - H[k - 1], mod)
    else:
        ret = dp[k] * 2 + (ret - dp[k])



print(ret)
# print(acc)
# print(c)
# 40, 96 , 4

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7


n = I()
H = LI() + [1]
A = [0] * n
r = 1
ret = 1
ans = 1
dd  = 1
for k in range(n - 1, -1, -1):
    if H[k - 1] == 1 and H[k + 1] == 1:
        ans = ans * pow(2, H[k], mod) % mod
    elif H[k] == 1:
        r = 1
        ret = 1
        ans = ans * 2 % mod
    elif H[k - 1] == 1:
        d = min(H[k], H[k + 1])
        ret = ret * 2 + r * (pow(2, d, mod) - 2)
        ans = ans * ret % mod
        ans = ans * pow(2, max(H[k] - max(H[k - 1], H[k + 1]), 0), mod)
    else:
        if H[k] > H[k - 1] and H[k + 1] > H[k - 1]:
            if H[k] > H[k + 1]:
                d = H[k + 1] - H[k - 1]
            else:
                d = H[k] - H[k - 1]
            ret = ret + r * (pow(2, d, mod) - 1)
            r = r * pow(2, d, mod) % mod
        ret = ret * 2 % mod
        ans = ans * pow(2, max(H[k] - max(H[k - 1], H[k + 1]), 0), mod)



print(ans % mod)
# print(acc)
# print(c)
# 40, 96 , 4

Submission status: Time Limit Exceeded

Solution code:
import sys
readline = sys.stdin.readline

MOD = 10**9+7
def compress(L):
    L2 = list(set(L))
    L2.sort()
    C = {v : k for k, v in enumerate(L2)}
    return L2, C

N = int(readline())
height = [0]
H = list(map(int, readline().split()))
height.extend(H)

orih, C = compress(height)

L = len(orih)

dp = [0]*L
dp[0] = 1

phidx = 0
for i in range(1, N+1):
    hidx = C[H[i-1]]
    dp2 = [0]*L
    if phidx >= hidx:
        for h in range(hidx+1):
            dp2[h] = (dp[hidx]+dp[h])%MOD
    else:
        if phidx == 0:
            dp2[0] = pow(2, orih[hidx])
            for h in range(1, hidx+1):
                dp2[h] = pow(2,  orih[hidx]-orih[h]+1, MOD)
        else:
            for h in range(hidx+1):
                dp2[h] = (dp[phidx] + dp[min(phidx, h)])*pow(2, orih[hidx]-orih[max(h, phidx)])%MOD
    dp = dp2[:]
    phidx = hidx
    #print(dp)
print(dp[0])

Submission status: Accepted

Solution code:

"""

https://atcoder.jp/contests/agc026/tasks/agc026_d

10101100011
01010011100

→1列目を決めたとする
→2列目の置き方は、左端を決めればすべて決まる
偶数列目を反転してみる？

10 → 11
01    00

10 → 11
10    11

すなわち、偶数列目が反転して表示されるとすると

全て01を入れ替える or 全てそのまま　しか許されない
→すべてそのままが可能なのは全て0 or 1のときのみ

dp[i][0][X] = i列目の下からX個まですべて0の時の通り数
dp[i][1][X] = i列目の下からX個まですべて1の時の通り数
→答えは dp[i][0][0]

if h[i-1] >= h[i]:
    dp[i][0][X] = dp[i-1][1][X] + dp[i-1][0][h[i]]
    dp[i][1][X] = dp[i-1][0][X] + dp[i-1][1][h[i]]
else:
    if X <= h[i-1]:
        dp[i][0][X] = (dp[i-1][1][X] + dp[i-1][0][h[i-1]]) * pow(2,h[i]-h[i-1],mod)
        dp[i][1][X] = (dp[i-1][0][X] + dp[i-1][1][h[i-1]]) * pow(2,h[i]-h[i-1],mod)
    else:
        dp[i][0][X] = (dp[i-1][1][h[i-1]] + dp[i-1][0][h[i-1]]) * pow(2,h[i]-X,mod)
        dp[i][1][X] = (dp[i-1][0][h[i-1]] + dp[i-1][1][h[i-1]]) * pow(2,h[i]-X,mod)

"""

from sys import stdin

N = int(stdin.readline())
h = list(map(int,stdin.readline().split()))
mod = 10**9+7

dp = [ [{},{}] for i in range(N) ]
numlis = set()
numlis.add(1)
for i in h:
    numlis.add(i)
for i in numlis:
    if i <= h[0]:
        dp[0][0][i] = pow(2,h[0]-i,mod)
        dp[0][1][i] = pow(2,h[0]-i,mod)

for i in range(1,N):

    for X in numlis:
        if X > h[i]:
            continue

        if h[i-1] >= h[i]:
            dp[i][0][X] = (dp[i-1][1][X] + dp[i-1][0][h[i]]) % mod
            dp[i][1][X] = (dp[i-1][0][X] + dp[i-1][1][h[i]]) % mod
        else:
            if X <= h[i-1]:
                dp[i][0][X] = (dp[i-1][1][X] + dp[i-1][0][h[i-1]]) * pow(2,h[i]-h[i-1],mod) % mod
                dp[i][1][X] = (dp[i-1][0][X] + dp[i-1][1][h[i-1]]) * pow(2,h[i]-h[i-1],mod) % mod
            else:
                dp[i][0][X] = (dp[i-1][1][h[i-1]] + dp[i-1][0][h[i-1]]) * pow(2,h[i]-X,mod) % mod
                dp[i][1][X] = (dp[i-1][0][h[i-1]] + dp[i-1][1][h[i-1]]) * pow(2,h[i]-X,mod) % mod

print ((dp[N-1][0][1] + dp[N-1][1][1]) % mod)

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7

n = I()
H = LI() + [1]
dp = [1] * (n + 1)

for k in range(n):
    new_dp = [0] * (n + 1)
    for i in range(n + 1):
        if H[i] > H[k]:
            new_dp[i] = dp[k] * 2
        elif H[k - 1] <= H[i]:
            new_dp[i] = dp[i] * 2 * pow(2, H[k] - H[i], mod)
        elif H[k - 1] > H[k]:
            new_dp[i] = dp[i] + dp[k]
        else:
            new_dp[i] = (dp[i] + dp[k - 1]) * pow(2, H[k] - H[k - 1], mod)
        new_dp[i] %= mod
    dp = new_dp


print(dp[-1])

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7

n = I()
H = LI() + [1]
dp = [1] * (n + 1)

for k in range(n):
    new_dp = [0] * (n + 1)
    for i in range(n + 1):
        if H[i] > H[k]:
            new_dp[i] = dp[k] * 2
        elif H[k - 1] <= H[i]:
            new_dp[i] = dp[i] * 2 * pow(2, H[k] - H[i], mod)
        elif H[k - 1] > H[k]:
            new_dp[i] = dp[i] - dp[k] + dp[k] * 2
        else:
            new_dp[i] = (dp[i] - dp[k - 1] + dp[k - 1] * 2) * pow(2, H[k] - H[k - 1], mod)
        new_dp[i] %= mod
    dp = new_dp


print(dp[-1])

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7

n = I()
H = LI() + [1]
dp = [1] * (n + 1)

for k in range(n):
    new_dp = [0] * (n + 1)
    for i in range(n + 1):
        if H[i] <= H[k]:
            if H[k - 1] <= H[i]:
                new_dp[i] = dp[i] * 2 * pow(2, H[k] - H[i], mod)
            elif H[k - 1] > H[k]:
                new_dp[i] = dp[i] - dp[k] + dp[k] * 2
            else:
                new_dp[i] = (dp[i] - dp[k - 1] + dp[k - 1] * 2) * pow(2, H[k] - H[k - 1], mod)
        else:
            new_dp[i] = dp[k] * 2
        new_dp[i] %= mod
    dp = new_dp


print(dp[-1])

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7

n = I()
H = LI() + [1]
dp = [0] * (n + 1)
ret = pow(2, H[0], mod)
for kk in range(n + 1):
    if H[0] >= H[kk]:
        dp[kk] = pow(2, H[0] - H[kk], mod) * 2
    else:
        dp[kk] = 2


for k in range(1, n):
    new_dp = [0] * (n + 1)
    for i in range(n + 1):
        if H[i] <= H[k]:
            if H[k - 1] <= H[i]:
                new_dp[i] = dp[i] * 2 * pow(2, H[k] - H[i], mod)
            elif H[k - 1] > H[k]:
                new_dp[i] = dp[i] - dp[k] + dp[k] * 2
            else:
                new_dp[i] = (dp[i] - dp[k - 1] + dp[k - 1] * 2) * pow(2, H[k] - H[k - 1], mod)
        else:
            new_dp[i] = dp[k] * 2
        new_dp[i] %= mod
    dp = new_dp


print(dp[-1])

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline

MOD = 10**9+7
def compress(L):
    L2 = list(set(L))
    L2.sort()
    C = {v : k for k, v in enumerate(L2)}
    return L2, C

N = int(readline())
height = [0]
H = list(map(int, readline().split()))
height.extend(H)

orih, C = compress(height)

L = len(orih)

dp = [0]*L
dp[0] = 1

phidx = 0
for i in range(1, N+1):
    hidx = C[H[i-1]]
    dp2 = [0]*L
    if phidx >= hidx:
        for h in range(hidx+1):
            dp2[h] = (dp[hidx]+dp[h])%MOD
    else:
        if phidx == 0:
            dp2[0] = pow(2, orih[hidx])%MOD
            for h in range(1, hidx+1):
                dp2[h] = pow(2,  orih[hidx]-orih[h]+1, MOD)
        else:
            for h in range(hidx+1):
                dp2[h] = (dp[phidx] + dp[min(phidx, h)])*pow(2, orih[hidx]-orih[max(h, phidx)], MOD)%MOD
    dp = dp2[:]
    phidx = hidx
    #print(dp)
print(dp[0])

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline
readlines = sys.stdin.readlines

import numpy as np

MOD = 10**9 + 7

N = int(readline())
H = [int(x) for x in readline().split()]

# 「初の同色」の位置によって場合分け。座圧して、近い区間のものは和をまとめて持つようにする。

H_unique = sorted(set([0,1]+H))
H_to_I = {h:i for i,h in enumerate(H_unique)}

items = [0] + [y-x for x,y in zip(H_unique,H_unique[1:])]

inv = pow(2,MOD-2,MOD)
coef = np.array([(pow(2,x+1,MOD)-2) * pow(inv,h,MOD) % MOD for x,h in zip(items,H_unique)],np.int64)

dp = np.zeros(len(H_unique),np.int64)
dp[0] = 1
I1,H1 = 1,1
for H2 in H:
    I2 = H_to_I[H2]
    prev = dp
    dp = np.zeros_like(prev)
    if I1 < I2:
        dp[0] = 2*prev[0]
        dp[1:I1+1] = prev[1:I1+1] * pow(2,H2-H1,MOD)
        dp[I1+1:I2+1] = coef[I1+1:I2+1] * pow(2,H2,MOD) % MOD * prev[0] % MOD
    else:
        prev[0] += prev[I2+1:].sum()
        dp += prev
        dp[0] *= 2
        dp[I2+1:] = 0
    dp %= MOD
    I1,H1 = I2,H2

answer = dp.sum()%MOD
print(answer)

Submission status: Accepted

Solution code:

import sys
#sys.stdin=open("data.txt")
input=sys.stdin.readline

MOD=10**9+7

def powmod(b,e):
    global MOD
    if e==0: return 1
    if e&1: return (powmod((b*b)%MOD,e//2)*b)%MOD
    return powmod((b*b)%MOD,e//2)

n=int(input())
h=[1]+list(map(int,input().split()))

"""
# naive solution, O(sum h_i)
archive=[]

# do rows
a1=[1]
for i in range(1,n+1):
    if h[i]<=h[i-1]:
        c=0
        while len(a1)>h[i]:
            c+=a1.pop(-1)
        a1[0]=((a1[0]+c)*2)%MOD
    else:
        a1[0]=(a1[0]*2)%MOD
        mul=powmod(2,h[i]-h[i-1])
        for j in range(1,len(a1)):
            a1[j]=(a1[j]*mul)%MOD
        extras=[a1[0]]
        for _ in range(h[i]-h[i-1]-1):
            extras.append(extras[-1]*2)
        a1+=extras[::-1]
    archive.append(a1)

print(sum(a1)%MOD)
"""

# smarter solution? i think it's O(N^2)
root=1      # number of times that this column just alternates
pos=[]      # [x,y] means it starts at x, and its size is y blocks
sz=1
for i in range(1,n+1):
    if h[i]<=h[i-1]:
        c=0
        while pos and sz-pos[-1][1]>=h[i]:
            a,b=pos.pop(-1)
            c+=(a*(powmod(2,b)-1))%MOD
            sz-=b
        if sz>h[i]:
            a,b=pos.pop(-1)
            pos.append([(a*powmod(2,sz-h[i]))%MOD,b-(sz-h[i])])
            c+=(a*(powmod(2,sz-h[i])-1))%MOD
            sz=h[i]
        root=((root+c)*2)%MOD
    else:
        root=(root*2)%MOD
        mul=powmod(2,h[i]-h[i-1])
        for j in range(len(pos)):
            pos[j][0]=(pos[j][0]*mul)%MOD
        pos.append([root,h[i]-h[i-1]])
        sz=h[i]

# get answer
for a,b in pos:
    root+=(a*(powmod(2,b)-1))%MOD
print(root%MOD)

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define ll long long
#define ld long double
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define SZ(x) (int)(x).size()
template <typename T> using ord_set = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int N = 105, MOD = 1e9 + 7;
int n, h[N], mn[N][N], dp[2][N][N], same[N][N], g[N][N], p[N];

int bp(int x, int y) {
	int res = 1;
	while (y) {
		if (y & 1)
			res = (ll)res * x % MOD;
		x = (ll)x * x % MOD;
		y /= 2;
	}
	return res;
}

void add(int & x, int y) {
	x += y;
	if (x >= MOD) x -= MOD;
}

int get(int l, int r) {
	if (l > r) return 1;
	int & res = g[l][r];
	if (res != -1) return res;
	return res = (ll)bp(2, max(0, h[l] - max(h[l - 1], mn[l + 1][r + 1]))) * get(l + 1, r) % MOD;
}

int solve(int f, int l, int r) {
	if (l > r) return 1;
	int & res = dp[f][l][r];
	if (res != -1) return res;
	res = 0;
	if (f == 0) {
		for (int i = l; i <= r; i++)
			add(res, (ll)get(l, i) * solve(1, i + 1, r) % MOD);
	}	else {
		for (int i = l + 1; i <= r; i++)
			add(res, (ll)same[l][i] * solve(0, i + 1, r) % MOD);
	}
	return res;
}

int main() {
	ios_base::sync_with_stdio(false), cin.tie(NULL);
	#ifdef LOCAL
		freopen("input.txt", "r", stdin);
	#endif
	
	memset(& g, -1, sizeof(g));
	memset(& dp, -1, sizeof(dp));
	cin >> n;
	int mul = 0;
	for (int i = 1; i <= n; i++) {
		cin >> h[i];
		if (h[i] == 1) mul++, h[i] = 0;
	}
	for (int r = n + 1; r >= 1; r--) {
		mn[r][r] = h[r];
		for (int l = r - 1; l >= 1; l--) {
			mn[l][r] = min(h[l], mn[l + 1][r]);
		}
	}
	p[0] = 1;
	for (int i = 1; i <= n; i++) {
		for (int j = 0; j <= i - 2; j++) {
			add(p[i], p[j]);
		}
	}
	for (int l = 1; l <= n; l++) {
		for (int r = l; r <= n; r++) {
			same[l][r] = 1;
			for (int k = l; k <= r; k++) {
				int hl = (k == l) ? 0 : h[k - 1];
				int hr = (k == r) ? 0 : h[k + 1];
				same[l][r] = (ll)same[l][r] * bp(2, max(0, h[k] - max(hl, hr))) % MOD;
			}
			same[l][r] = (ll)same[l][r] * p[r - l + 1] % MOD;
		}
	}
	int last = 0, res = 1;
	for (int i = 1; i <= n + 1; i++) {
		if (h[i] == 0) {
			if (last + 1 <= i - 1) {
				int cur = (solve(0, last + 1, i - 1) + solve(1, last + 1, i - 1)) % MOD;
				cur = cur * 2 % MOD;
				cur = (cur - get(last + 1, i - 1) + MOD) % MOD;
				res = (ll)res * cur % MOD;
			}
			last = i;
		}
	}
	cout << (ll)res * bp(2, mul) % MOD;
}

Submission status: Runtime Error

Solution code:
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)

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

const LL MOD = 1000000007;
LL powmod(LL a, LL n){
    if(n == 0) return 1;
    if(n % 2) return (a*powmod(a,n-1)) % MOD;
    LL c = powmod(a, n/2);
    return (c*c) % MOD;
}
LL inv(LL a){
    return powmod(a, MOD-2);
}
LL fact[110000];
LL invfact[110000];

LL ncr(LL n, LL r){
    if(r < 0 || n < 0) return 0;
    if(n < r) return 0;
    LL a = fact[n];
    a = (a * invfact[r]) % MOD;
    a = (a * invfact[n-r]) % MOD;
    return a;
}
void init(){
    fact[0] = 1;
    invfact[0] = 1;
    LL inv2 = inv(2);
    for(LL i = 1; i < 110000; i++){
        fact[i] = (i*fact[i-1]) % MOD;
        invfact[i] = inv(fact[i]);
    }
}

pair<LL,LL> solve(vector<LL> a){
	LL r = a[0];
	for(int j = 0; j < a.size(); j++){
		r = min(r, a[j]);
	}
	LL num0 = 0;
	for(int j = 0; j < a.size(); j++){
		a[j] -= r;
		if(a[j] == 0) num0++;
	}
	vector<LL> cur;
	LL total = powmod(2, num0);
	LL alternating = 2;
	a.push_back(0);

	for(int j = 0; j < a.size(); j++){
		if(a[j] == 0 && cur.size() > 0){
			pair<LL,LL> d = solve(cur);
			cur.clear();
			total = (total * (d.first + d.second) ) % MOD;
			alternating = (alternating * d.second) % MOD;
		}
		if(a[j] != 0){
			cur.push_back(a[j]);
		}
		if(a[j] == 0){
			num0 ++;
		}
	}
	total -= alternating;
	alternating = (alternating * powmod(2, r-1)) % MOD;
	total += alternating;
	total %= MOD;
	if(total < 0) total += MOD;
	if(alternating < 0) alternating += MOD;
	return {total, alternating};
}
int main(){
	LL N;
	cin >> N;
	vector<LL> h;
	for(int i = 0; i < N; i++){
		LL a;
		cin >> a;
		h.push_back(a);
	}
	pair<LL,LL> ans = solve(h);
	cout << ans.first << endl;
}