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:
#!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[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()

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 aaa[:i]:
        if l > r:
            mf.add_link(r, l + n, INF)
print(mf.max_flow(0, t))

Submission status: Accepted

Solution code:
N,A,B=map(int,input().split())
p=list(map(int,input().split()))
p=[p[i]-1 for i in range(N)]

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

for j in range(N+1):
    if p[0]<=j:
        dp[0][j]=0
    else:
        dp[0][j]=A

for i in range(1,N):
    for j in range(N+1):
        if p[i]<=j:
            dp[i][j]=min(dp[i-1][p[i]],dp[i-1][j]+B)
        else:
            dp[i][j]=dp[i-1][j]+A

print(dp[-1][N])

Submission status: Accepted

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

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

data=[0]*(N+1)
flag=[0]*(N+1)
for i in range(N):
    p=P[i]
    flag[p]=1
    cnt=0
    for j in range(p+1,N+1):
        if flag[j]==0:
            data[j]=data[j-1]
        else:
            cnt+=1
            data[j]=min(cnt*A+data[p-1],data[j]+B)

print(data[-1])

Submission status: Accepted

Solution code:
N, A, B = map(int, input().split())
P = [int(a) - 1 for a in input().split()]
X = [0] * N
for i in range(N):
    pre = X
    X = [0] * N
    mi = pre[0]
    for j in range(N):
        mi = min(mi, pre[j])
        X[j] = mi + (A if j < P[i] else B if j > P[i] else 0)
print(min(X))

Submission status: Accepted

Solution code:

"""

Writer: SPD_9X2
https://atcoder.jp/contests/agc032/tasks/agc032_d

圧倒的挿入ソート
https://atcoder.jp/contests/abc006/tasks/abc006_4
これの、左右のコストが違うVer

最長部分増加列を計算すれば、A=Bの時の答えは分かる
その時の答えは, A * (N - 最長部分増加列の長さ)

残りのカードが昇順になるように抜き出し、適切な場所に戻す。
最長部分列として採用する or しないで dp?

dp[i][部分増加列の最後の数字] = i番目まで見た時のコストの最小値 かな？

増加列の最後に足せば、コストはかからない
足さないとき、最後の数字より大きければ、A払う
小さければ、B払う

O(N**2)で解けた？
"""

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

p = list(map(int,input().split()))

dp = [float("inf")] * (N+1)
dp[0] = 0

for i in range(N):

    ndp = [float("inf")] * (N+1)

    for j in range(N+1):

        if p[i] >= j: #p[i]よりjがおおきいので、Aコスト & 更新ができる
            ndp[j] = min(ndp[j] , dp[j] + A)
            ndp[p[i]] = min(ndp[p[i]] , dp[j])

        else: #Bコストでの更新
            ndp[j] = min(ndp[j] , dp[j] + B)

    dp = ndp
print (min(dp))

Submission status: Accepted

Solution code:
n, a, b = map(int, input().split())
p = list(map(int, input().split()))

INF = 10**13
dp = [[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 j < p[i]:
			dp[i+1][p[i]] = min(dp[i+1][p[i]], dp[i][j])
			dp[i+1][j] = min(dp[i+1][j], dp[i][j] + a)
		else:
			dp[i+1][j] = min(dp[i+1][j], dp[i][j] + b)

print(min(dp[n]))

Submission status: Accepted

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

N, A, B = map(int, readline().split())
P = list(map(int, readline().split()))

INF = 1<<64

dp = [INF]*(N+1)
dp[0] = 0

for i in range(N):
    p = P[i]
    dp2 = [INF]*(N+1)
    for j in range(N+1):
        if p < j:
            dp2[j] = dp[j] + B
        if j < p:
            dp2[p] = min(dp2[p], dp[j])
            dp2[j] = dp[j] + A
    dp = dp2
print(min(dp))

Submission status: Accepted

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

    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
    bigger = [[0] * (N+1) for _ in range(N+1)]
    for p in range(1, N+1):
        for j in range(N):
            if P[j] > p:
                bigger[p][j+1] = bigger[p][j] + 1
            else:
                bigger[p][j + 1] = bigger[p][j]
    #print(bigger)
    inf = 10**14
    dp = [[inf] * (N+1) for _ in range(N+1)]
    dp[0][0] = 0

    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 * (bigger[p][i] - bigger[p][j]))
            else:
                dp[p][j] = min(dp[p][j], dp[p - 1][j])
    print(min(dp[-1]))
    #[print(i, dp[i]) for i in range(N+1)]


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from numpy import *
N,A,B,*P=map(int,open(0).read().split());d=full(N+1,1<<60,'int');d[0]=0
for p in P:d[p]=min(d[:p]);d[p+1:]+=B;d[:p]+=A
print(min(d))

Submission status: Accepted

Solution code:
import numpy as np
N,A,B,*P=map(int,open(0).read().split())
dp=np.full(N+1,10**18,np.int64)
dp[0]=0
for p in P:
    dp[p]=min(dp[:p])
    dp[p+1:]+=B
    dp[:p]+=A
print(min(dp))

Submission status: Accepted

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

import numpy as np

"""
各数字ごとに左移動・右移動・そのまま使う。全部コスト1ならLIS。
左から見て、「最後にそのまま使った数、そこまでの数を並べるコスト」を持ってdp。
"""

N,A,B = map(int,input().split())
P = [int(x) for x in input().split()]

INF = 10**18
dp = np.full(N+1,INF,dtype=np.int64)
dp[0] = 0
for p in P:
    # pを置く
    dp[p] = dp[:p].min()
    # pを左移動
    dp[p+1:] += B
    # pを右移動
    dp[:p] += A

answer = dp.min()
print(answer)

Submission status: Accepted

Solution code:
n, a, b = map(int, input().split())
dp = [0] + [2 ** 60] * n
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] += [b, a][p[j] < p[i]]
print(min(dp))

Submission status: Accepted

Solution code:
N,A,B=map(int,input().split())
P=[int(i) for i in input().split()]
s=1e19
d=[s]*(N+1)
d[0]=0
for i in range(N):
    e=[s]*(N+1)
    for j in range(N+1):
        if j < P[i]:
            e[P[i]]=min(e[P[i]],d[j])
            e[j]=min(e[j],d[j]+A)
        else:
            e[j]=min(e[j],d[j]+B)
    d=e
print(min(d))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from bisect import bisect
from operator import itemgetter

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

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))
    remain = iter(dp[s:])
    for j, cost in remain:
        if stay_cost > cost + a:
            ndp.append((j, cost + a))
            break
    ndp.extend((j, cost + a) for j, cost in remain)
    dp = ndp
print(dp[-1][1])

Submission status: Accepted

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))
    remain = iter(dp[s:])
    for j, cost in remain:
        if stay_cost > cost + a:
            ndp.append((j, cost + a))
            break
    ndp.extend((j, cost + a) for j, cost in remain)
    dp = ndp
print(dp[-1][1])

Submission status: Accepted

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

N, A, B = map(int, readline().split())
*P, = map(int, readline().split())
Q = [0]*N
for i, p in enumerate(P):
    Q[p-1] = i

INF = 10**18
dp = [[INF]*(N+1) for i in range(N+1)]
dp[0][0] = 0
for i in range(N):
    qi = Q[i]
    for j in range(N):
        v = dp[i][j]
        dp[i+1][j] = min(dp[i+1][j], v + (A if qi < j else B))
        dp[i][j+1] = min(dp[i][j+1], v)
        if Q[i] == j:
            dp[i+1][j+1] = min(dp[i+1][j+1], v)
for i in range(N):
    dp[i+1][N] = min(dp[i+1][N], dp[i][N] + A)
for j in range(N):
    dp[N][j+1] = min(dp[N][j+1], dp[N][j])
sys.stdout.write("%d\n" % dp[N][N])

Submission status: Runtime Error

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()))
    start = time.time()
    # 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: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10000)

n, a, b = map(int, input().split())
p = list(map(int, input().split()))
p.append(n+1)
p.insert(0,0)
#'''
#print (p)

INF = (a+b)*n
min_ans =INF   # 仮のmin値

# l-shift で　右端を整列する
def ptr_l_shift(p, cost, l, r):
    for i in range(l, r+1):
        if p[i] == r :
            if r == i:
                return (0 + solve(p, cost, l, r-1))
            # l_shift(l, r)
            p =    p[0:i] +p[i+1:r+1] +p[i:i+1] +p[r+1:]
            ret = solve(p, cost, l, r-1)
            p =    p[0:i] +p[r:r+1] +p[i:r] +p[r+1:]
            return (a + ret)
#    print("error l_shift", p,l,r)


# r-shift で　左端を整列する
def ptr_r_shift(p, cost, l, r) :
    for i in range(l, r+1):
        if p[i] == l :
            if i == l :
                return (0 + solve(p, cost, l+1, r))
            # r_shift(i, j)
            p =    p[0:l] +p[i:i+1] +p[l:i] +p[i+1:]
            ret = solve(p, cost, l+1, r)
            p =    p[0:l] +p[l+1:i+1] +p[l:l+1] +p[i+1:]
            return (b + ret)
#    print("error r_shift", p,l,r)

def solve(p, cost, ptr_l, ptr_r):
    global min_ans 
    if cost >= min_ans :
        return (INF)

    if ptr_l == ptr_r :
        if cost < min_ans :
            min_ans = cost
        return (0)

    if a < b :    # コストの小さい方を優先する
        ll = ptr_l_shift(p, cost, ptr_l, ptr_r) 
        rr = ptr_r_shift(p, cost, ptr_l, ptr_r) 
    else:
        rr = ptr_r_shift(p, cost, ptr_l, ptr_r) 
        ll = ptr_l_shift(p, cost, ptr_l, ptr_r) 

#    print ("return ll, rr =", ll, rr)
    if ll > rr :
#        if rr < min_ans :
#            min_ans = rr
        return (rr)
    else :
#        if ll < min_ans :
#            min_ans = ll
        return (ll)

cost = 0
print (solve(p, cost, 1, n))

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10000)

n, a, b = map(int, input().split())
p = list(map(int, input().split()))
p.append(n+1)
p.insert(0,0)
#'''
#print (p)

INF = (a+b)*n
min_ans =INF   # 仮のmin値

# l-shift で　右端を整列する
def ptr_l_shift(p, cost, l, r):
    for i in range(l, r+1):
        if p[i] == r :
            if r == i:
                return (0 + solve(p, cost, l, r-1))
            # l_shift(l, r)
            p =    p[0:i] +p[i+1:r+1] +p[i:i+1] +p[r+1:]
            ret = solve(p, cost, l, r-1)
            p =    p[0:i] +p[r:r+1] +p[i:r] +p[r+1:]
            return (a + ret)
#    print("error l_shift", p,l,r)


# r-shift で　左端を整列する
def ptr_r_shift(p, cost, l, r) :
    for i in range(l, r+1):
        if p[i] == l :
            if i == l :
                return (0 + solve(p, cost, l+1, r))
            # r_shift(i, j)
            p =    p[0:l] +p[i:i+1] +p[l:i] +p[i+1:]
            ret = solve(p, cost, l+1, r)
            p =    p[0:l] +p[l+1:i+1] +p[l:l+1] +p[i+1:]
            return (b + ret)
#    print("error r_shift", p,l,r)

def solve(p, cost, ptr_l, ptr_r):
    global min_ans 
    if cost >= min_ans :
        return (INF)

    if ptr_l == ptr_r :
        return (0)

    if a < b :    # コストの小さい方を優先する
        ll = ptr_l_shift(p, cost, ptr_l, ptr_r) 
        rr = ptr_r_shift(p, cost, ptr_l, ptr_r) 
    else:
        rr = ptr_r_shift(p, cost, ptr_l, ptr_r) 
        ll = ptr_l_shift(p, cost, ptr_l, ptr_r) 

#    print ("return ll, rr =", ll, rr)
    if ll > rr :
        if rr < min_ans :
            min_ans = rr
        return (rr)
    else :
        if ll < min_ans :
            min_ans = ll
        return (ll)

cost = 0
print (solve(p, cost, 1, n))

Submission status: Runtime Error

Solution code:
# AGC032 Problem-D1


n, a, b = map(int, input().split())
#global p 
p = list(map(int, input().split()))
p.append(n+1)
p.insert(0,0)
#print (p)

# l-shift で　右端を整列する
def ptr_l_shift(p, l, r):
    for i in range(l, r+1):
        if p[i] == r :
            if r == i:
                return (0 + solve(p, l, r-1))
            # l_shift(l, r)
#            print ("l_shift i=", i, "r=",r)
#            print (p[0:i], p[i:i+1], p[i+1:r+1], p[r+1:])
            p =    p[0:i] +p[i+1:r+1] +p[i:i+1] +p[r+1:]
#            print (p)
            ret = solve(p, l, r-1)
#            print ("r_shift  l=", l, "i=",i)
#            print (p[0:i], p[i:r], p[r:r+1], p[r+1:])
            p =    p[0:i] +p[r:r+1] +p[i:r] +p[r+1:]
#            print (p)
            return (a + ret)
#    print("error l_shift", p,l,r)


# r-shift で　左端を整列する
def ptr_r_shift(p, l, r) :
    for i in range(l, r+1):
        if p[i] == l :
            if i == l :
                return (0 + solve(p, l+1, r))
            # r_shift(i, j)
#            print ("r_shift  l=", l, "i=",i)
#            print (p[0:l], p[l:i], p[i:i+1], p[i+1:])
            p =    p[0:l] +p[i:i+1] +p[l:i] +p[i+1:]
#            print (p)
            ret = solve(p, l+1, r)
#            print ("l_shift i=", i, "r=",r)
#            print (p[0:l], p[l:l+1], p[l+1:i+1], p[i+1:])
            p =    p[0:l] +p[l+1:i+1] +p[l:l+1] +p[i+1:]
#            print (p)
            return (b + ret)
#    print("error r_shift", p,l,r)

def solve(p, ptr_l, ptr_r):
    if (ptr_l, ptr_r) in memo :
        return (memo[ptr_l, ptr_r])

    if ptr_l == ptr_r :
        return (0)
    
    ll = ptr_l_shift(p, ptr_l, ptr_r) 
    rr = ptr_r_shift(p, ptr_l, ptr_r) 
#    print ("return ll, rr =", ll, rr)
    if ll > rr :
        memo[(ptr_l, ptr_r)] = rr
        return (rr)
    else :
        memo[(ptr_l, ptr_r)] = ll
        return (ll)

memo = {}

print (solve(p, 1, n))
#print ("ans =", solve(p, 1, n))

Submission status: Runtime Error

Solution code:
# AGC032 Problem-D1


n, a, b = map(int, input().split())
#global p 
p = list(map(int, input().split()))
p.append(n+1)
p.insert(0,0)
#print (p)

# l-shift で　右端を整列する
def ptr_l_shift(p, l, r):
    for i in range(l, r+1):
        if p[i] == r :
            if r == i:
                return (0 + solve(p, l, r-1))
            # l_shift(l, r)
#            print ("l_shift i=", i, "r=",r)
#            print (p[0:i], p[i:i+1], p[i+1:r+1], p[r+1:])
            p =    p[0:i] +p[i+1:r+1] +p[i:i+1] +p[r+1:]
#            print (p)
            ret = solve(p, l, r-1)
#            print ("r_shift  l=", l, "i=",i)
#            print (p[0:l], p[l:i], p[i:i+1], p[i+1:])
            p =    p[0:l] +p[i:i+1] +p[l:i] +p[i+1:]
#            print (p)
            return (a + ret)
#    print("error l_shift", p,l,r)


# r-shift で　左端を整列する
def ptr_r_shift(p, l, r) :
    for i in range(l, r+1):
        if p[i] == l :
            if i == l :
                return (0 + solve(p, l+1, r))
            # r_shift(i, j)
#            print ("r_shift  l=", l, "i=",i)
#            print (p[0:l], p[l:i], p[i:i+1], p[i+1:])
            p =    p[0:l] +p[i:i+1] +p[l:i] +p[i+1:]
#            print (p)
            ret = solve(p, l+1, r)
#            print ("l_shift i=", i, "r=",r)
#            print (p[0:i], p[i:i+1], p[i+1:r+1], p[r+1:])
            p =    p[0:i] +p[i+1:r+1] +p[i:i+1] +p[r+1:]
#            print (p)
            return (b + ret)
#    print("error r_shift", p,l,r)

def solve(p, ptr_l, ptr_r):
    if (ptr_l, ptr_r) in memo :
        return (memo[ptr_l, ptr_r])

    if ptr_l == ptr_r :
        return (0)
    
    ll = ptr_l_shift(p, ptr_l, ptr_r) 
    rr = ptr_r_shift(p, ptr_l, ptr_r) 
#    print ("return ll, rr =", ll, rr)
    if ll > rr :
        memo[(ptr_l, ptr_r)] = rr
        return (rr)
    else :
        memo[(ptr_l, ptr_r)] = ll
        return (ll)

memo = {}

print (solve(p, 1, n))
#print ("ans =", solve(p, 1, n))

Submission status: Runtime Error

Solution code:
# AGC032 Problem-D

n, a, b = map(int, input().split())
#global p 
p = list(map(int, input().split()))
p.append(n+1)
p.insert(0,0)
#print (p)

# l-shift で　右端を整列する
def ptr_l_shift(p, l, r):
    for i in range(l, r+1):
        if p[i] == r :
            if r == i:
                return (0 + solve(p, l, r-1))
            # l_shift(l, r)
#            print ("l_shift i=", i, "r=",r)
#            print (p[0:i], p[i:i+1], p[i+1:r+1], p[r+1:])
            p =    p[0:i] +p[i+1:r+1] +p[i:i+1] +p[r+1:]
#            print (p)
            return (a + solve(p, l, r-1))
    return(0)
#    print("error l_shift", p,l,r)


# r-shift で　左端を整列する
def ptr_r_shift(p, l, r) :
    for i in range(l, r+1):
        if p[i] == l :
            if i == l :
                return (0 + solve(p, l+1, r))
            # r_shift(i, j)
#            print ("r_shift  l=", l, "i=",i)
#            print (p[0:l], p[l:i], p[i:i+1], p[i+1:])
            p =    p[0:l] +p[i:i+1] +p[l:i] +p[i+1:]
#            print (p)
            return (b + solve(p, l+1, r))
    return(0)
#    print("error r_shift", p,l,r)

def solve(p, ptr_l, ptr_r):
    if (ptr_l, ptr_r) in memo :
        return (memo[ptr_l, ptr_r])

    if ptr_l == ptr_r :
        return (0)
    
    ll = ptr_l_shift(p[:], ptr_l, ptr_r) 
    rr = ptr_r_shift(p[:], ptr_l, ptr_r) 
#    print ("return ll, rr =", ll, rr)
    if ll > rr :
        memo[(ptr_l, ptr_r)] = rr
        return (rr)
    else :
        memo[(ptr_l, ptr_r)] = ll
        return (ll)

memo = {}

print (solve(p, 1, n))
#print ("ans =", solve(p, 1, n))


'''
def r_shift(l, r) :
    global p
    print ("r_shft  l=", l, "r=",r)
    print (p[0:l], p[l:r], p[r:r+1], p[r+1:n+1])
    p =    p[0:l] +p[r:r+1] +p[l:r] +p[r+1:n+1]
    print (p)
    return

def l_shift(l, r) :
    global p
    print ("l_shift l=", l, "r=",r)
    print (p[0:l], p[l:l+1], p[l+1:r+1], p[r+1:])
    p =    p[0:l] +p[l+1:r+1] +p[l:l+1] +p[r+1:]
    print (p)
    return
'''

Submission status: Runtime Error

Solution code:
# AGC032 Problem-D

n, a, b = map(int, input().split())
#global p 
p = list(map(int, input().split()))
p.append(n+1)
p.insert(0,0)
#print (p)

# l-shift で　右端を整列する
def ptr_l_shift(p, l, r):
    for i in range(l, r+1):
        if p[i] == r :
            if r == i:
                return (0 + solve(p, l, r-1))
            # l_shift(l, r)
#            print ("l_shift i=", i, "r=",r)
#            print (p[0:i], p[i:i+1], p[i+1:r+1], p[r+1:])
            p =    p[0:i] +p[i+1:r+1] +p[i:i+1] +p[r+1:]
#            print (p)
            return (a + solve(p, l, r-1))
#    print("error l_shift", p,l,r)


# r-shift で　左端を整列する
def ptr_r_shift(p, l, r) :
    for i in range(l, r+1):
        if p[i] == l :
            if i == l :
                return (0 + solve(p, l+1, r))
            # r_shift(i, j)
#            print ("r_shift  l=", l, "i=",i)
#            print (p[0:l], p[l:i], p[i:i+1], p[i+1:])
            p =    p[0:l] +p[i:i+1] +p[l:i] +p[i+1:]
#            print (p)
            return (b + solve(p, l+1, r))
#    print("error r_shift", p,l,r)

def solve(p, ptr_l, ptr_r):
    if (ptr_l, ptr_r) in memo :
        return (memo[ptr_l, ptr_r])

    if ptr_l == ptr_r :
        return (0)
    
    ll = ptr_l_shift(p[:], ptr_l, ptr_r) 
    rr = ptr_r_shift(p[:], ptr_l, ptr_r) 
#    print ("return ll, rr =", ll, rr)
    if ll > rr :
        memo[(ptr_l, ptr_r)] = rr
        return (rr)
    else :
        memo[(ptr_l, ptr_r)] = ll
        return (ll)

memo = {}

print (solve(p, 1, n))
#print ("ans =", solve(p, 1, n))

Submission status: Runtime Error

Solution code:
#include <cstring>
#include <iostream>

using namespace std;

#define MAX_N 5000
#define INF 0x3f3f3f3f

long dp[MAX_N + 1][MAX_N + 1];
int x0[MAX_N + 1], P[MAX_N];

long rotation_sort( int N, int A, int B )
{
    for ( int i = 0; i < N; i++ ) x0[P[i]] = i;

    memset( dp, INF, sizeof( dp ) );
    memset( dp[0], 0, sizeof( dp[0] ) );

    for ( int k = 1; k <= N; k++ )
    {
        long min_prev = INF;

        for ( int x = 0; x <= N; x++ )
        {
            int cost;
            if ( x == x0[k] )
                cost = 0;
            else if ( x < x0[k] )
                cost = B;
            else
                cost = A;

            min_prev = min( min_prev, dp[k - 1][x] );
            dp[k][x] = min_prev + cost;
        }
    }

    long ans = INF;
    for ( auto v : dp[N] ) ans = min( ans, v );

    return ans;
}

int main( int argc, char **argv )
{
    long N, A, B;
    cin >> N >> A >> B;

    for ( int i = 0; i < N; i++ ) cin >> P[i];

    cout << rotation_sort( N, A, B ) << endl;

    return 0;
}

Submission status: Runtime Error

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: 1000_000_000_000_000)
    tmp_min_cost = 1000_000_000_000_000
    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: Runtime Error

Solution code:
from functools import*
@lru_cache(None)
def solve(p):
    #print(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: Runtime Error

Solution code:
from functools import*
@lru_cache(None)
def solve(p):
    print(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)))