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: Runtime Error

Solution code:
def solve(p):
    print(p)
    if len(p)<2:
        return 0
    i=p.index(max(p))
    return min(solve(p[:i])+(len(p)-1-i)*b,solve(p[:i]+p[i+1:])+a)
n,a,b,*p=map(int,open(0).read().split())
print(solve(p))

Submission status: Runtime Error

Solution code:
n, m = [int(i) for i in input().split()]
E = [[] for i in range(n+1)]
used = [False] * (n + 1)
IN = [0] * (n + 1)

for i in range(m):
    a, b = [int(i) for i in input().split()]
    E[a].append(b)
    E[b].append(a)
    IN[a] += 1
    IN[b] += 1

cnt_4 = 0
cnt_6 = 0
v_4 = []
for j, i in enumerate(IN[1:]):
    if i % 2 == 1 or i == 0:
        print('No')
        exit()
    if i >= 4:
        cnt_4 += 1
        v_4.append(j + 1)
    if i >= 6:
        cnt_6 += 1

def dfs(p, v):
    if v == v_4[0]:
        return v_4[0]
    if v == v_4[1]:
        return v_4[1]

    for e in E[v]:
        if e == p:
            continue
        return dfs(v, e)

if cnt_4 > 2 or cnt_6 >= 1:
    print('Yes')
elif cnt_4 == 2:
    if all(dfs(v_4[0], e) == v_4[1] for e in E[v_4]):
        print('No')
    else:
        print('Yes')

else:
    print('No')

Submission status: Runtime Error

Solution code:
ri = lambda: int(input())
rl = lambda: list(map(int,input().split()))
rr = lambda N: [ri() for _ in range(N)]
YN = lambda b: print('YES') if b else print('NO')
yn = lambda b: print('Yes') if b else print('No')
OE = lambda x: print('Odd') if x%2 else print('Even')
INF = 10**18

N,A,B=rl()
P=rl()

for i in range(N):
    P[i] -= (i+1)

ans = 0
while True:
    abs_max = -1
    ind = 0
    for i in range(N):
        a_p = abs(P[i])
        if abs_max < a_p:
            abs_max = a_p
            ind = i
    if abs_max == 0:
        break

    if P[ind] > 0:
        ans += min(B,A*P[ind])
        for i in range(ind+1,ind+P[ind]+1):
            P[i] += 1
        P[ind] = 0
    else:
        ans += min(A,B*(-P[ind]))
        for i in range(ind+P[ind],ind):
            P[i] -= 1
        P[ind] = 0


print(ans)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat Feb 16 20:52:46 2019

@author: Owner
"""


import collections
import scipy.misc
import sys
import numpy as np
import math
from operator import itemgetter
import itertools
import copy
import bisect

#素因数を並べる
def prime_decomposition(n):
  i = 2
  table = []
  while i * i <= n:
    while n % i == 0:
      n /= i
      table.append(int(i))
    i += 1
  if n > 1:
    table.append(int(n))
  return table   
# 桁数を吐く
def digit(i):
    if i > 0:
        return digit(i//10) + [i%10]
    else:
        return []
    
def getNearestValueIndex(list, num):
    """
    概要: リストからある値に最も近い値のインデックスを取得する関数
    @param list: データ配列
    @param num: 対象値
    @return 対象値に最も近い値
    """

    # リスト要素と対象値の差分を計算し最小値のインデックスを取得
    idx = np.abs(np.asarray(list) - num).argmin()
    return idx

def find_index(l, x, default=False):
    if x in l:
        return l.index(x)
    else:
        return default


"""
N, X = map(int, input().split())

x = [0]*N
x[:] = map(int, input().split())

P = [0]*N
Y = [0]*N
for n in range(N):
    P[n], Y[n] = map(int, input().split())

    
all(nstr.count(c) for c in '753')

# 複数配列を並び替え
ABT = zip(A, B, totAB)
result = 0
# itemgetterには何番目の配列をキーにしたいか渡します
sorted(ABT,key=itemgetter(2))
A, B, totAB = zip(*ABT)
A.sort(reverse=True)

# 2進数のbit判定
(x >> i) & 1

# dp最小化問題
dp = [np.inf]*N
for n in range(N):
    if n == 0:
        dp[n] = 0
    else:
        for k in range(1,K+1):
            if n-k >= 0:
                dp[n] = min(dp[n], dp[n-k] + abs(h[n]-h[n-k]))
            else:
                break

"""

N, A, B = map(int, input().split())

p = [0]*N
p[:] = map(int, input().split())
p_end = find_index(p, 1)
cost = 0
for i in range(N-1):
    n = i+2
    i_idx = find_index(p,n)
    tmp_p = p[i_idx]
    if p_end == i_idx+1:
        p_end += 1 
    elif p_end > i_idx:
        cost += A
        p[i_idx:p_end] = p[i_idx+1:p_end+1] 
        p[p_end] = tmp_p
    else:
        cost += B
        p[p_end+2:i_idx+1] = p[p_end+1:i_idx] 
        p[p_end+1] = tmp_p
        p_end += 1
print(cost)

Submission status: Runtime Error

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(2):
        p = pf.copy()
        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()

Submission status: Runtime Error

Solution code:
n = int(input())
list = []
a = []
for i in range(n):
  list.append(int(input))

for i in range(1, n):
  for j in range(1, i):
    if list[i] == j:
      a.insert(j, j)

if a == list:
  for i in range(n):
    print(list[i])
else:
  print(-1)