Problem:


Score : 1000 points

Problem Statement

You are given a permutation p = (p_1, \ldots, p_N) of \{ 1, \ldots, N \}.
You can perform the following two kinds of operations repeatedly in any order:

Pay a cost A. Choose integers l and r (1 \leq l < r \leq N), and shift (p_l, \ldots, p_r) to the left by one. That is, replace p_l, p_{l + 1}, \ldots, p_{r - 1}, p_r with p_{l + 1}, p_{l + 2}, \ldots, p_r, p_l, respectively.

Pay a cost B. Choose integers l and r (1 \leq l < r \leq N), and shift (p_l, \ldots, p_r) to the right by one.  That is, replace p_l, p_{l + 1}, \ldots, p_{r - 1}, p_r with p_r, p_l, \ldots, p_{r - 2}, p_{r - 1}, respectively.

Find the minimum total cost required to sort p in ascending order.

Constraints

All values in input are integers.

1 \leq N \leq 5000

1 \leq A, B \leq 10^9

(p_1 \ldots, p_N) is a permutation of \{ 1, \ldots, N \}.

Input

Input is given from Standard Input in the following format:

N A B
p_1 \cdots p_N

Output

Print the minimum total cost required to sort p in ascending order.

Sample Input 1

3 20 30
3 1 2

Sample Output 1

20

Shifting (p_1, p_2, p_3) to the left by one results in p = (1, 2, 3).

Sample Input 2

4 20 30
4 2 3 1

Sample Output 2

50

One possible sequence of operations is as follows:

Shift (p_1, p_2, p_3, p_4) to the left by one. Now we have p = (2, 3, 1, 4).

Shift (p_1, p_2, p_3) to the right by one. Now we have p = (1, 2, 3, 4).

Here, the total cost is 20 + 30 = 50.

Sample Input 3

1 10 10
1

Sample Output 3

0

Sample Input 4

4 1000000000 1000000000
4 3 2 1

Sample Output 4

3000000000

Sample Input 5

9 40 50
5 3 4 7 6 1 2 9 8

Sample Output 5

220



Sample input:
3 20 30
3 1 2


Sample output:
20

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    input = sys.stdin.readline

    class Bit:
        def __init__(self, n):
            self.size = n
            self.tree = [0] * (n + 1)

        def sum(self, i):
            s = 0
            while i > 0:
                s += self.tree[i]
                i -= i & -i
            return s

        def add(self, i, x):
            while i <= self.size:
                self.tree[i] += x
                i += i & -i

    N, R, L = map(int, input().split())
    P = list(map(int, input().split()))

    val2idx = [0] * (N+1)
    for i, p in enumerate(P):
        val2idx[p] = i + 1
    inf = 10**14
    dp = [[inf] * (N+1) for _ in range(N+1)]
    dp[0][0] = 0
    bit = Bit(N+1)
    for p in range(1, N+1):
        i = val2idx[p]
        for j in range(N+1):
            if i > j:
                dp[p][j] = min(dp[p][j], dp[p-1][j] + L)
                dp[p][i] = min(dp[p][i], dp[p-1][j] + R * (i - j - 1 - (bit.sum(i) - bit.sum(j))))
            else:
                dp[p][j] = min(dp[p][j], dp[p - 1][j])
        bit.add(i, 1)
    print(min(dp[-1]))
    #[print(i, dp[i]) for i in range(N+1)]


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
  n, a, b = map(int, input().split())
  plist = list(map(int, input().split()))
  dp = [float('inf')] * (n+1)
  dp[0] = 0
  for i in range(n):
    tmp_dp = [float('inf')] * (n+1)
    for j in range(n+1):
      if dp[j] == float('inf'):
        continue
      if plist[i] > j:
        if tmp_dp[plist[i]] > dp[j]:
          tmp_dp[plist[i]] = dp[j]
        if tmp_dp[j] > dp[j] + a:
          tmp_dp[j] = dp[j] + a
      else:
        if tmp_dp[j] > dp[j] + b:
          tmp_dp[j] = dp[j] + b
    dp = tmp_dp

  ans = float('inf')
  for i in range(n+1):
    if ans > dp[i]:
      ans = dp[i]
  print(ans)


if __name__ == '__main__':
  main()

Submission status: Time Limit Exceeded

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

def main():
  n, a, b = map(int, input().split())
  plist = list(map(int, input().split()))
  dp = [[float('inf') for _ in range(n+1)] for _ in range(n+1)]
  dp[0][0] = 0
  for i in range(n):
    for j in range(n+1):
      if dp[i][j] == float('inf'):
        continue
      if plist[i] > j:
        if dp[i+1][plist[i]] > dp[i][j]:
          dp[i+1][plist[i]] = dp[i][j]
        if dp[i+1][j] > dp[i][j] + a:
          dp[i+1][j] = dp[i][j] + a
      else:
        if dp[i+1][j] > dp[i][j] + b:
          dp[i+1][j] = dp[i][j] + b

  ans = float('inf')
  for i in range(n+1):
    if ans > dp[n][i]:
      ans = dp[n][i]
  print(ans)


if __name__ == '__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys
import numpy as np
### 方針
### 1から順番にソートをしようとすると最小試行回数を満たせない
### 本来の場所からの距離を探索し、遠い+昇順で選択
### 本来の数列ではなく、本来の場所からの距離を計算し、距離だけでソートを計算する

def turn_Left(c,start,end):
    if (end - start > 1):
        target_num=c[start]+end-start
        for i in range(start,end):
            c[i] = c[i+1] - 1
        c[end] = target_num
    else:
        c[start]=0
        c[end]=0
    return c

def turn_Right(c,start,end):
    if (end - start > 1):
        target_num=c[end]-end+start
        for i in reversed(range(start+1,end+1)):
            c[i] = c[i-1] + 1
        c[start] = target_num
    else:
        c[start]=0
        c[end]=0
    return c

def AtCoder_d(c,c_left,c_right):
    if (abs(max(c)) > abs(min(c))):
        if (max(c)*c_left > c_right ):
            cost = c_right
            c = turn_Right(c,np.argmax(c)-max(c),np.argmax(c))
        else:
            cost = c_left
            c = turn_Left(c,np.argmax(c)-max(c),np.argmax(c))
    else:
        if (abs(min(c))*c_right > c_left ):
            cost = c_left
            c = turn_Left(c,np.argmin(c),np.argmin(c)+abs(min(c)))
        else:
            cost = c_right
            c = turn_Right(c,np.argmin(c),np.argmin(c)+abs(min(c)))
    return c,cost

if __name__ == '__main__':
    # 標準入力を受け取る
    a = list(map(int,input().split()))
    b = list(map(int,input().split()))
    # a[0]：N、a[1]：左に移動するコスト、a[2]:右に移動するコスト
    c=[0]*a[0]
    c_left=a[1]
    c_right=a[2]
    # 本来の位置(正しい順列状態)との各数字の距離を計算
    for i in range(a[0]):
        c[i]=i + 1 - b[i]
    #cost初期化
    cost=0
    #既に昇順に並んでいる場合を弾きつつ、ソート開始
    while True:
        if ( max(c) == 0 and min(c) == 0 ):
            break
        if (max(c) == 1 and min(c) == -1):
            cost += min(c_left,c_right)*c.count(1)
            break
        result = AtCoder_d(c,c_left,c_right)
        c = result[0]
        cost = cost + result[1]
    print(cost)

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np

### 方針
### ソートの実行時間は最大でもN^2 / 2で収まるはず
### 1から順番にソートをしようとすると最小試行回数を満たせない
### 本来の場所からの距離を探索し、遠い+昇順で選択
### 本来の数列ではなく、本来の場所からの距離を計算し、距離だけでソートを計算する

def turn_Left(c,start,end):
    if (end - start > 1):
        target_num=c[start]+end-start
        for i in range(start,end):
            c[i] = c[i+1] - 1
        c[end] = target_num
    else:
        c[start]=0
        c[end]=0
    return c

def turn_Right(c,start,end):
    if (end - start > 1):
        target_num=c[end]-end+start
        for i in reversed(range(start+1,end+1)):
            c[i] = c[i-1] + 1
        c[start] = target_num
    else:
        c[start]=0
        c[end]=0
    return c

def AtCoder_d(c,c_left,c_right):
    if (abs(max(c)) > abs(min(c))):
        if (max(c)*c_left > c_right ):
            cost = c_right
            c = turn_Right(c,np.argmax(c)-max(c),np.argmax(c))
        else:
            cost = c_left
            c = turn_Left(c,np.argmax(c)-max(c),np.argmax(c))
    else:
        if (abs(min(c))*c_right > c_left ):
            cost = c_left
            c = turn_Left(c,np.argmin(c),np.argmin(c)+abs(min(c)))
        else:
            cost = c_right
            c = turn_Right(c,np.argmin(c),np.argmin(c)+abs(min(c)))
    return c,cost

if __name__ == '__main__':
    # 標準入力を受け取る
    a = list(map(int,input().split()))
    b = list(map(int,input().split()))
    # a[0]：N、a[1]：左に移動するコスト、a[2]:右に移動するコスト
    c=[0]*a[0]
    c_left=a[1]
    c_right=a[2]
    # 本来の位置(正しい順列状態)との各数字の距離を計算
    for i in range(a[0]):
        c[i]=i + 1 - b[i]
    #cost初期化
    cost=0
    #既に昇順に並んでいる場合を弾きつつ、ソート開始
    while True:
        if ( max(c) == 0 and min(c) == 0 ):
            break
        result = AtCoder_d(c,c_left,c_right)
        c = result[0]
        cost = cost + result[1]
    print(cost)

Submission status: Time Limit Exceeded

Solution code:
N,A,B=map(int,input().split())
P=[int(i) for i in input().split()]
dp=[[10**19]*(N+1) for i in range(N+1)]
dp[0][0]=0
for i in range(1,N+1):
    for j in range(N+1):
        #if dp[i-1][j]==10**19:
            #continue
        if j < P[i-1]:
            dp[i][P[i-1]]=min(dp[i][P[i-1]],dp[i-1][j])
            dp[i][j]=min(dp[i][j],dp[i-1][j]+A)
        else:
            dp[i][j]=min(dp[i][j],dp[i-1][j]+B)
#print(dp)
print(min(dp[-1]))

Submission status: Time Limit Exceeded

Solution code:
def rotation_sort(N: int, A: int, B: int, P: list) -> int:
    # x0[v] = v の P 内での初期位置
    x0 = {v: i for i, v in enumerate(P)}

    # dp[k][x] = k が x0[k] から開区間 (x-1, x) に移動するときの最小コスト
    # k が (x-1, x) に移動する際の最小コストは x0->(x-1, x) の移動コストを
    # C とすると
    # dp[k][x] = min(dp[k-1][0], ..., dp[k-1][x])
    dp = [[float('inf')] * (N+1) for _ in range(N+1)]
    dp[0] = [0] * (N+1)

    for k in range(1, N+1):
        # 要素 k-1 が (-inf, x+1) へ移動するための最小コスト
        min_prev = float('inf')
        for x in range(N+1):
            if x == x0[k]:
                # 移動なし
                cost = 0
            elif x < x0[k]:
                # 左移動
                cost = B
            else:
                # 右移動
                cost = A
            min_prev = min(min_prev, dp[k-1][x])
            dp[k][x] = min_prev + cost

    return min(dp[N])


if __name__ == "__main__":
    N, A, B = map(int, input().split())
    P = [int(s) for s in input().split()]

    ans = rotation_sort(N, A, B, P)
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect

n, a, b = map(int, input().split())
ppp = map(int, input().split())
qqq = [0] * n
for i, p in enumerate(ppp, start=1):
    qqq[p - 1] = i

dp = [(0, 0)]
for i in qqq:
    s = bisect(dp, (i,))
    ndp = [(j, cost + b) for j, cost in dp[:s]]
    stay_cost = dp[s - 1][1]
    ndp.append((i, stay_cost))
    ndp.extend((j, cost + a) for j, cost in dp[s:] if stay_cost > cost + a)
    dp = ndp
print(dp[-1][1])

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect
from operator import itemgetter

n, a, b = map(int, input().split())
ppp = map(int, input().split())
qqq = [i for i, p in sorted(enumerate(ppp, start=1), key=itemgetter(1))]
INF = 10 ** 15

dp = [(0, 0)]
for i in qqq:
    s = bisect(dp, (i,))
    ndp = [(j, cost + b) for j, cost in dp[:s]]
    stay_cost = dp[s - 1][1]
    ndp.append((i, stay_cost))
    ndp.extend((j, cost + a) for j, cost in dp[s:] if stay_cost > cost + a)
    dp = ndp
print(dp[-1][1])

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect
from operator import itemgetter

n, a, b = map(int, input().split())
ppp = map(int, input().split())
qqq = [i for i, p in sorted(enumerate(ppp, start=1), key=itemgetter(1))]
INF = 10 ** 15

dp = [(0, 0)]
for i in qqq:
    ndp = []
    s = bisect(dp, (i,))
    tmp_min = INF
    for j, cost in dp[:s]:
        cost += b
        ndp.append((j, cost))
        tmp_min = cost
    stay_cost = dp[s - 1][1]
    if tmp_min > stay_cost:
        ndp.append((i, stay_cost))
        tmp_min = stay_cost
    for j, cost in dp[s:]:
        cost += a
        if tmp_min > cost:
            ndp.append((j, cost))
            tmp_min = cost
    dp = ndp

print(dp[-1][1])

Submission status: Time Limit Exceeded

Solution code:
from operator import itemgetter

n, a, b = map(int, input().split())
ppp = list(map(int, input().split()))
qqq = list(map(itemgetter(0), sorted(enumerate(ppp, start=1), key=itemgetter(1))))
INF = 10 ** 15

dp = {0: 0}
for i in qqq:
    ndp = {}
    tmp_min_cost = INF
    stay_min_cost = INF
    for j, cost in sorted(dp.items()):
        if j <= i:
            if j < i:
                stay_min_cost = min(stay_min_cost, cost)
            cost += b
            if tmp_min_cost > cost:
                ndp[j] = tmp_min_cost = cost
        else:
            cost += a
            if tmp_min_cost > cost:
                ndp[j] = tmp_min_cost = cost
    if stay_min_cost < INF:
        ndp[i] = min(ndp[i], stay_min_cost) if i in ndp else stay_min_cost
    dp = ndp

print(min(dp.values()))

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
from operator import itemgetter

n, a, b = map(int, input().split())
ppp = list(map(int, input().split()))
qqq = list(map(itemgetter(0), sorted(enumerate(ppp, start=1), key=itemgetter(1))))

dp = {0: 0}
for i in qqq:
    ndp = defaultdict(lambda: 1000000000000000)
    tmp_min_cost = 1000000000000000
    for j, cost in sorted(dp.items()):
        if cost >= tmp_min_cost:
            continue
        tmp_min_cost = cost
        if j < i:
            ndp[i] = min(ndp[i], cost)
            ndp[j] = min(ndp[j], cost + b)
        else:
            ndp[j] = min(ndp[j], cost + a)
    dp = ndp

print(min(dp.values()))

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
from operator import itemgetter

n, a, b = map(int, input().split())
ppp = list(map(int, input().split()))
qqq = list(map(itemgetter(0), sorted(enumerate(ppp, start=1), key=itemgetter(1))))

dp = {0: 0}
for i in qqq:
    ndp = defaultdict(lambda: 10 ** 18)
    tmp_min_cost = 10 ** 18
    for j, cost in sorted(dp.items()):
        if cost >= tmp_min_cost:
            continue
        tmp_min_cost = cost
        if j < i:
            ndp[i] = min(ndp[i], cost)
            ndp[j] = min(ndp[j], cost + b)
        else:
            ndp[j] = min(ndp[j], cost + a)
    dp = ndp

print(min(dp.values()))

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
from operator import itemgetter

n, a, b = map(int, input().split())
ppp = list(map(int, input().split()))
qqq = list(map(itemgetter(0), sorted(enumerate(ppp, start=1), key=itemgetter(1))))

dp = {0: 0}
for i in qqq:
    ndp = defaultdict(lambda: 10 ** 18)
    for j, cost in dp.items():
        if j < i:
            ndp[i] = min(ndp[i], cost)
            ndp[j] = min(ndp[j], cost + b)
        else:
            ndp[j] = min(ndp[j], cost + a)
    dp = ndp

print(min(dp.values()))

Submission status: Time Limit Exceeded

Solution code:
def main():
    from functools import lru_cache
    from bisect import bisect,insort
    import sys
    sys.setrecursionlimit(10**9)
    @lru_cache(None)
    def solve(n,m):
        l=r=N=M=0
        for j,v in enumerate(i[1:n],1):
            if v<m:
                if v<i[n]:
                    l+=1
                    N=max(N,j)
                else:
                    r+=1
            M=max(M,j)
        if l+r<1:
            return 0
        return min(solve(M,m)+a,solve(N,i[n])+r*b)
        
    n,a,b,*p=map(int,open(0).read().split())
    i=[0]*-~n
    for j,v in enumerate(p):
        i[v]=j
    print(solve(n,n))
if __name__=='__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n, a, b = map(int, input().split())
dp = [2 ** 60] * (n + 1)
dp[0] = 0
p = list(map(int, input().split()))
for i in range(n):
    dp[i + 1] = dp[0]
    dp[0] += a
    for j in range(i):
        if p[j] < p[i]:
            dp[i + 1] = min(dp[i + 1], dp[j + 1])
            dp[j + 1] += a
        else:
            dp[j + 1] += b
print(min(dp))

Submission status: Time Limit Exceeded

Solution code:
def main():
    from functools import lru_cache
    from bisect import bisect,insort
    import sys
    sys.setrecursionlimit(10**9)
    @lru_cache(None)
    def solve(p):
        if len(p)<2:
            return 0
        n=len(p)
        j=i[n]
        x=sorted(p[:j])
        z={}
        for k in range(j):
          z[x[k]]=k
        q=t(z[i]for i in p[:j])
        r=p[:j]+p[j+1:]
        x=sorted(r)
        z={}
        for k in range(n-1):
          z[x[k]]=k
        r=t(z[i]for i in r)
        return min(solve(q)+(n-1-j)*b,solve(r)+a)
    n,a,b,*p=map(int,open(0).read().split())
    l=[0]*-~n
    for i,v in enumerate(p):
        l[v]=i
    t=[]
    i=[0]*-~n
    for j,v in enumerate(l[1:],1):
        i[j]=bisect(t,v)
        insort(t,v)
    t=tuple
    print(solve(t(p)))
if __name__=='__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    from functools import lru_cache
    from bisect import bisect,insort
    import sys
    sys.setrecursionlimit(10**9)
    @lru_cache(None)
    def solve(p):
        if len(p)<2:
            return 0
        j=i[len(p)]
        return min(solve(t(p[:j]))+(len(p)-1-j)*b,solve(t(p[:j]+p[j+1:]))+a)
    n,a,b,*p=map(int,open(0).read().split())
    l=[0]*-~n
    for i,v in enumerate(p):
        l[v]=i
    t=[]
    i=[0]*-~n
    for j,v in enumerate(l[1:],1):
        i[j]=bisect(t,v)
        insort(t,v)
    t=tuple
    print(solve(t(p)))
if __name__=='__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    from functools import lru_cache
    import sys
    sys.setrecursionlimit(10**9)
    @lru_cache(None)
    def solve(p):
        if len(p)<2:
            return 0
        j=i[len(p)]
        return min(solve(t(p[:j]))+(len(p)-1-j)*b,solve(t(p[:j]+p[j+1:]))+a)
    n,a,b,*p=map(int,open(0).read().split())
    i=[0]*-~n
    for j,v in enumerate(p):
        i[v]=j-sum(t>v for t in p[:j])
    t=tuple
    print(solve(t(p)))
if __name__=='__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from functools import*
import sys
sys.setrecursionlimit(10**9)
@lru_cache(None)
def solve(p):
    if len(p)<2:
        return 0
    i=p.index(max(p))
    return min(solve(t(p[:i]))+(len(p)-1-i)*b,solve(t(p[:i]+p[i+1:]))+a)
n,a,b,*p=map(int,open(0).read().split())
t=tuple
print(solve(t(p)))

Submission status: Time Limit Exceeded

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007
sys.setrecursionlimit(1000000)

#A
def A():
    n = I()
    b = LI()
    ans = []
    d = max(b)
    i = 0
    while b:
        j = len(b)-1
        while j >= 0:
            if b[j] > j+1:
                print(-1)
                quit()
            elif b[j] == j+1:
                ans.append(b[j])
                b.pop(j)
                break
            j -= 1
    for i in ans[::-1]:
        print(i)
#B
def B():
    n = I()
    if n%2:
        ans = []
        for i in range(1,n+1):
            for j in range(1,n+1):
                if j != n-i and j != i:
                    ans.append((min(i,j),max(i,j)))
        ans = list(set(ans))
        print(len(ans))
        ans.sort()
        for i in ans:
            print(*i)
    else:
        ans = []
        for i in range(1,n+1):
            for j in range(1,n+1):
                if j != n+1-i and j != i:
                    ans.append((min(i,j),max(i,j)))
        ans = list(set(ans))
        print(len(ans))
        ans.sort()
        for i in ans:
            print(*i)
#C
def C():
    return

#D
def D():
    n,a,b = LI()
    p = LI()
    ans = 0
    l = [p[i] for i in range(n)]
    l.sort()
    f = defaultdict(int)
    for i in p:
        f[i] = l.index(i)
    ans = 0
    while l != p:
        d = []
        i = 0
        while i < n:
            j = i
            while j < n-1:
                if f[p[j+1]] != f[p[j]]+1:break
                j += 1
            d.append([p[i:j+1],i])
            i = j+1
        m = len(d)
        ld = [d[i][0] for i in range(m)]
        ld.sort()
        fd = defaultdict(int)
        for i,j in d:
            fd[str(i)] = ld.index(i)
        for i in range(m)[::-1]:
            if d[i][0] != ld[i]:
                j = fd[str(d[i][0])]
                x = d[i]
                if j > i:
                    k = d[j][1]-d[i][1]
                    p = len(d[i][0])
                    ans += min(b*k,a*p)
                    d.pop(i)
                    d.insert(j,x)
                    break
                else:
                    k = d[i][1]-d[j][1]
                    p = len(d[i][0])
                    ans += min(a*k,b*p)
                    d.pop(i)
                    d.insert(j,x)
                    break
        p = [None for i in range(n)]
        s = 0
        for i in range(m):
            for j in range(len(d[i][0])):
                p[s+j] = d[i][0][j]
            s += len(d[i][0])
    print(ans)

#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == "__main__":
    D()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque


class Dinic:
    def __init__(self, n):
        self.n = n
        self.links = [[] for _ in range(n)]
        self.depth = None
        self.progress = None

    def add_link(self, _from, to, cap):
        self.links[_from].append([cap, to, len(self.links[to])])
        self.links[to].append([0, _from, len(self.links[_from]) - 1])

    def bfs(self, s):
        depth = [-1] * self.n
        depth[s] = 0
        q = deque([s])
        while q:
            v = q.popleft()
            for cap, to, rev in self.links[v]:
                if cap > 0 and depth[to] < 0:
                    depth[to] = depth[v] + 1
                    q.append(to)
        self.depth = depth

    def dfs(self, v, t, flow):
        if v == t:
            return flow
        links_v = self.links[v]
        for i in range(self.progress[v], len(links_v)):
            self.progress[v] = i
            cap, to, rev = link = links_v[i]
            if cap == 0 or self.depth[v] >= self.depth[to]:
                continue
            d = self.dfs(to, t, min(flow, cap))
            if d == 0:
                continue
            link[0] -= d
            self.links[to][rev][0] += d
            return d
        return 0

    def max_flow(self, s, t):
        flow = 0
        while True:
            self.bfs(s)
            if self.depth[t] < 0:
                return flow
            self.progress = [0] * self.n
            current_flow = self.dfs(s, t, float('inf'))
            while current_flow > 0:
                flow += current_flow
                current_flow = self.dfs(s, t, float('inf'))


n, a, b = map(int, input().split())
aaa = list(map(int, input().split()))
mf = Dinic(2 * n + 2)
t = 2 * n + 1
for i in range(1, n + 1):
    mf.add_link(0, i, b)
    mf.add_link(n + i, t, a)
INF = 10 ** 18
for i in range(n):
    r = aaa[i]
    for l in reversed(aaa[:i]):
        if l > r:
            mf.add_link(r, l + n, INF)
        if l + 1 == r:
            mf.add_link(r, l, INF)
            break
print(mf.max_flow(0, t))

Submission status: Time Limit Exceeded

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007
sys.setrecursionlimit(1000000)

#A
def A():
    n = I()
    b = LI()
    ans = []
    d = max(b)
    i = 0
    while b:
        j = len(b)-1
        while j >= 0:
            if b[j] > j+1:
                print(-1)
                quit()
            elif b[j] == j+1:
                ans.append(b[j])
                b.pop(j)
                break
            j -= 1
    for i in ans[::-1]:
        print(i)
#B
def B():
    n = I()
    if n%2:
        ans = []
        for i in range(1,n+1):
            for j in range(1,n+1):
                if j != n-i and j != i:
                    ans.append((min(i,j),max(i,j)))
        ans = list(set(ans))
        print(len(ans))
        ans.sort()
        for i in ans:
            print(*i)
    else:
        ans = []
        for i in range(1,n+1):
            for j in range(1,n+1):
                if j != n+1-i and j != i:
                    ans.append((min(i,j),max(i,j)))
        ans = list(set(ans))
        print(len(ans))
        ans.sort()
        for i in ans:
            print(*i)
#C
def C():
    return

#D
def D():
    n,a,b = LI()
    pf = LI()
    f_ans = float("inf")
    l = [pf[i] for i in range(n)]
    l.sort()
    f = defaultdict(int)
    for i in pf:
        f[i] = l.index(i)
    for _ in range(1):
        p = [pf[i] for i in range(n)]
        ans = 0
        while l != p:
            d = []
            i = 0
            while i < n:
                j = i
                while j < n-1:
                    if f[p[j+1]] != f[p[j]]+1:break
                    j += 1
                d.append(p[i:j+1])
                i = j+1
            m = len(d)
            ld = [d[i] for i in range(m)]
            ld.sort()
            fd = defaultdict(int)
            for i in d:
                fd[str(i)] = ld.index(i)
            if _ == 0:
                for i in range(m)[::-1]:
                    if d[i] != ld[i]:
                        j = fd[str(d[i])]
                        x = d[i]
                        if j > i:
                            k = 0
                            for o in range(i+1,j+1):
                                k += len(d[o])
                            p = len(d[i])
                            ans += min(b*k,a*p)
                            d.pop(i)
                            d.insert(j,x)
                            break
                        else:
                            k = 0
                            for o in range(j,i):
                                k += len(d[o])
                            p = len(d[i])
                            ans += min(a*k,b*p)
                            d.pop(i)
                            d.insert(j,x)
                            break
            else:
                for i in range(m)[::-1]:
                    if d[i] != ld[i]:
                        j = fd[str(d[i])]
                        x = d[i]
                        if j > i:
                            k = 0
                            for o in range(i+1,j+1):
                                k += len(d[o])
                            p = len(d[i])
                            ans += min(b*k,a*p)
                            d.pop(i)
                            d.insert(j,x)
                            break
                        else:
                            k = 0
                            for o in range(j,i):
                                k += len(d[o])
                            p = len(d[i])
                            ans += min(a*k,b*p)
                            d.pop(i)
                            d.insert(j,x)
                            break
            p = [None for i in range(n)]
            s = 0
            for i in range(len(d)):
                for j in range(len(d[i])):
                    p[s+j] = d[i][j]
                s += len(d[i])
        f_ans = min(f_ans,ans)
    print(f_ans)

#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == "__main__":
    D()