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: Wrong Answer

Solution code:
n, a, b = map(int, input().split())
p = list(map(int, input().split()))
q = [0] * n
for i, x in enumerate(p):
    q[x - 1] = i
dp = [[0] * (n + 1) for _ in range(n + 1)]
mi = [[n] * (n + 1) for _ in range(n + 1)]
ma = [[0] * (n + 1) for _ in range(n + 1)]
for i in range(n + 1):
    for j in range(i + 1, n + 1):
        mi[i][j] = min(mi[i][j - 1], q[j - 1])
        ma[i][j] = max(ma[i][j - 1], q[j - 1])
for i in range(1, n + 1):
    for j in range(i + 1):
        k = i - j
        s, t = 1, 1
        if j > 0 and j == p[mi[j - 1][n - k]]:
            s = 0
        if k > 0 and n - k + 1 == p[ma[j][n - k + 1]]:
            t = 0
        if j == 0:
            dp[j][k] = dp[j][k - 1] + a * t
        elif k == 0:
            dp[j][k] = dp[j - 1][k] + b * s
        else:
            dp[j][k] = min(dp[j - 1][k] + b * s, dp[j][k - 1] + a * t)
ans = float('inf')
for i in range(n + 1):
    ans = min(ans, dp[i][n - i])
print(ans)

Submission status: Wrong Answer

Solution code:
n, a, b = 5000, 10000000, 10000000
p = list(range(n, 0, -1))
q = [0] * n
for i, x in enumerate(p):
    q[x - 1] = i
dp = [[0] * (n + 1) for _ in range(n + 1)]
mi = [[n] * (n + 1) for _ in range(n + 1)]
ma = [[0] * (n + 1) for _ in range(n + 1)]
for i in range(n + 1):
    for j in range(i + 1, n + 1):
        mi[i][j] = min(mi[i][j - 1], q[j - 1])
        ma[i][j] = max(ma[i][j - 1], q[j - 1])
for i in range(1, n + 1):
    for j in range(i + 1):
        k = i - j
        s, t = 1, 1
        if j > 0 and j == p[mi[j - 1][n - k]]:
            s = 0
        if k > 0 and n - k + 1 == p[ma[j][n - k + 1]]:
            t = 0
        if j == 0:
            dp[j][k] = dp[j][k - 1] + a * t
        elif k == 0:
            dp[j][k] = dp[j - 1][k] + b * s
        else:
            dp[j][k] = min(dp[j - 1][k] + b * s, dp[j][k - 1] + a * t)
ans = float('inf')
for i in range(n + 1):
    ans = min(ans, dp[i][n - i])
print(ans)

Submission status: Wrong Answer

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

moved = [False for _ in range(n+1)]
for i in range(1, n):
	tmp = 0
	will_be_moved = []
	for j in range(i):
		if p[j] > p[i] and not moved[p[j]]:
			tmp += a
			will_be_moved.append(j)
	if tmp > b:
		ans += b
		moved[p[i]] = True
	else:
		ans += tmp
		for m in will_be_moved:
			moved[p[m]] = True
print(ans)

Submission status: Wrong Answer

Solution code:
n, a, b = map(int, input().split())
p = list(map(int, input().split()))
ans = 0
for i in range(1, n+1):
	if i not in p:
		continue
	cur = 0
	tmp = 0
	while p[cur] != i:
		if p[cur] > i:
			tmp += a
		cur += 1
	if tmp > b:
		ans += b
		p = [x for x in p if x != i]
	else:
		for j in range(cur+1, len(p)):
			if p[j] < i:
				ans += a
				break
print(ans)

Submission status: Wrong Answer

Solution code:
n, a, b = map(int, input().split())
p = list(map(int, input().split()))
ans = 0
for i in range(1, n+1):
	if i not in p:
		continue
	cur = 0
	tmp = 0
	while p[cur] != i:
		if p[cur] > i:
			tmp += a
		cur += 1
	if tmp <= b:
		ans += tmp
		p = p[cur+1:]
	else:
		ans += b
	#p = [x for x in p if x != i]
print(ans)

Submission status: Wrong Answer

Solution code:
n, a, b = map(int, input().split())
p = list(map(int, input().split()))
ans = 0
for i in range(1, n+1):
	if i not in p:
		continue
	cur = 0
	tmp = 0
	while p[cur] != i:
		tmp += a
		cur += 1
	if tmp <= b:
		ans += tmp
		p = p[cur+1:]
	else:
		ans += b
		p = [x for x in p if x != i]
print(ans)

Submission status: Wrong Answer

Solution code:
from bisect import*
n,a,b,*p=map(int,open(0).read().split())
l=[]
c=0
for i,q in enumerate(p):
  j=bisect(l,q)
  if j!=len(l):
    r=len(l)-j
    c+=min(b,a*r)
    l[j]=q
  else:
    l.append(q)
print(c)

Submission status: Wrong Answer

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()
    dp = [[float("inf")]*(n+1) for i in range(n+1)]
    dp[0][0] = 0
    for i in range(n):
        for j in range(n):
            if p[i] == j:
                cost = 0
            elif p[i] < j:
                cost = b
            else:
                cost = a
            dp[i+1][j] = min(dp[i+1][j],dp[i][j]+cost)
            dp[i][j+1] = min(dp[i][j+1],dp[i][j])
            dp[i+1][j+1] = min(dp[i+1][j+1],dp[i][j]+cost)

    print(dp[n][n])
#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

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

Submission status: Wrong Answer

Solution code:
import sys

# Rotate selected partial list and return the full list
def reorder(list, index, newIndex):
    tmp = list
    ind = -1
    if index > newIndex:
        tmp.insert(newIndex, list[index])
        tmp.pop(index + 1)
    if index < newIndex:
        tmp.insert(newIndex + 1, list[index])
        tmp.pop(index)

    # print(2,tmp)
    return tmp


# Calculate the distance a element from its original position
def distance(element, set):
    return element - set.index(element) - 1


# Calculate the cheapest way to make a rotation
## to rotate a list of k elements to the right once
## is the same as to rotate k-1 times to the left
def add_cost(bef, aft):
    global A
    global B

    max_rot = abs(aft-bef)

    if bef > aft:
        if B > max_rot * A:
            return max_rot * A
        else:
            return B
    else:
        if A > max_rot * B:
            return max_rot * B
        else:
            return A


# Get input and assign the proper variables
input = [int(i) for i in sys.stdin.readline().split("\n")[0].split(" ")]

N = input[0]
A = input[1]
B = input[2]

lst = [int(i) for i in sys.stdin.readline().split("\n")[0].split(" ")]

# Sorted list for comparison
reordered = [i for i in range(1, N+1)]

## moved is a list of numbers that were rotated
moved = []
cost = 0


# Repeat until the original list is sorted
while not lst == reordered:

    dist = 0
    dest = 5001
    dist_tmp = 0
    indexCur = -1
    indexNew = -1

    # Select the element that is the furthest
    for i in lst:
        if i not in moved:
            dist_tmp = abs(distance(i, lst))
            if dist_tmp > dist:
                indexCur = lst.index(i)
                dist = dist_tmp

    # Find where to put the selected element
    if not dist == 1:
        for k in lst:
            if not k == lst[indexCur]:
                dist_tmp = abs(distance(k, lst))
                if dist_tmp < dest:
                    indexNew = lst.index(k)
                    dest = dist_tmp
                    continue
                if dist_tmp == dest:
                    if k < lst[indexCur]:
                        indexNew = lst.index(k)
                        continue

    # Final Stage
    # There are only 0s and 1s left
    else:
        try:
            if distance(lst[indexCur + 1],lst) == -1:
                indexNew = indexCur + 1
        # Already moved the element with the highest distance [5,2,3,1,4]
        except:
            if distance(lst[indexCur - 1], lst) == 1:
                indexNew = indexCur - 1

    # Move element and count Cost
    moved.append(lst[indexCur])
    if not indexNew == -1 and not indexCur == indexNew:
        # print(lst[indexCur], indexNew, add_cost(indexCur, indexNew))
        lst = reorder(lst, indexCur, indexNew)
        # print(lst)
        cost += add_cost(indexCur, indexNew)

print(cost)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
from bisect import bisect, insort
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 = []
    app = ndp.append
    for j, cost in dp:
        cost += b if j < i else a
        app((j, cost))
    stay_cost = dp[bisect(dp, (i,)) - 1][1]
    insort(ndp, (i, stay_cost))
    dp = ndp

print(min(cost for i, cost in dp))

Submission status: Wrong Answer

Solution code:
from bisect import bisect, insort
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 = []
    app = ndp.append
    tmp_min_cost = INF
    for j, cost in dp:
        cost += b if j < i else a
        if tmp_min_cost > cost:
            app((j, cost))
            tmp_min_cost = cost
    stay_cost = dp[bisect(dp, (i,)) - 1][1]
    insort(ndp, (i, stay_cost))
    dp = ndp

print(min(cost for i, cost in dp))

Submission status: Wrong Answer

Solution code:
from bisect import bisect, insort
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)]
stay_cost = 0
for i in qqq:
    ndp = []
    app = ndp.append
    tmp_min_cost = INF
    for j, cost in dp:
        cost += b if j < i else a
        if tmp_min_cost > cost:
            app((j, cost))
            tmp_min_cost = cost
    stay_cost = dp[bisect(dp, (i,)) - 1][1]
    insort(ndp, (i, stay_cost))
    dp = ndp

print(min(stay_cost, dp[-1][1]))

Submission status: Wrong Answer

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 = []
    app = ndp.append
    tmp_min_cost = INF
    for j, cost in dp:
        if j < i:
            cost += b
        else:
            cost += a
        if tmp_min_cost > cost:
            app((j, cost))
            tmp_min_cost = cost
    s = bisect(dp, (i,))
    stay_cost = dp[s - 1][1]
    item = (i, stay_cost)
    k = bisect(ndp, item)
    if len(ndp) == k:
        app(item)
    elif ndp[k - 1][0] == i:
        continue
    elif ndp[k][0] == i:
        ndp[k] = item
    else:
        ndp.insert(k, item)
    dp = ndp

print(dp[-1][1])

Submission status: Wrong Answer

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 = []
    app = ndp.append
    tmp_min_cost = INF
    stay_min_cost = INF
    for j, cost in dp:
        if j < i:
            stay_min_cost = cost
            cost += b
        else:
            cost += a
        if tmp_min_cost > cost:
            app((j, cost))
            tmp_min_cost = cost
    if stay_min_cost < INF:
        item = (i, stay_min_cost)
        k = bisect(ndp, item)
        if len(ndp) == k:
            app(item)
        elif ndp[k - 1][0] == i:
            continue
        elif ndp[k][0] == i:
            ndp[k] = item
        else:
            ndp.insert(k, item)
    dp = ndp

print(dp[-1][1])

Submission status: Wrong Answer

Solution code:
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 = []
    app = ndp.append
    tmp_min_cost = INF
    stay_min_cost = INF
    for j, cost in dp:
        if j <= i:
            stay_min_cost = cost
            cost += b
        else:
            cost += a
        if tmp_min_cost > cost:
            app((j, cost))
            tmp_min_cost = cost
    if stay_min_cost < INF:
        bisect.insort(ndp, (i, stay_min_cost))
    dp = ndp

print(dp[-1][1])

Submission status: Wrong Answer

Solution code:
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 = []
    app = ndp.append
    tmp_min_cost = INF
    stay_min_cost = INF
    for j, cost in dp:
        if j <= i:
            if j < i:
                stay_min_cost = cost
            cost += b
        else:
            cost += a
        if tmp_min_cost > cost:
            app((j, cost))
            tmp_min_cost = cost
    if stay_min_cost < INF:
        bisect.insort(ndp, (i, stay_min_cost))
    dp = ndp

print(dp[-1][1])

Submission status: Wrong Answer

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

print(qqq)

# 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: Wrong Answer

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
completed = [False] * (n + 1)
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('Time for Construct Graph')  # Test
exit()
print(mf.max_flow(0, t))

Submission status: Wrong Answer

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(n, p, p_end, i_idx)
print(cost)

Submission status: Wrong Answer

Solution code:
N, A, B = map(int, input().split())
P = list(map(int, input().split()))
Pmin = [None]*N
Pmax = [None]*N
for i, p in enumerate(P):
    k = 20000
    for pj in P[:i]:
        if pj > p:
            k = min(k, pj)
    Pmin[p-1] = k

for i, p in enumerate(P):
    k = -1
    for pj in P[:i:-1]:
        if pj < p:
            k = max(k, pj)
    Pmax[p-1] = k
dp = [[10**15]*(N+2) for _ in range(N+2)]
dp[1][N] = 0
for k in range(N-1, -1, -1):
    for i in range(1, N - k + 1):
        x = dp[i][i+k]
        if Pmax[i+k-1] + 1 <= i:
            dp[i][i+k-1] = min(dp[i][i+k-1], x)
        else:
            dp[i][i+k-1] = min(dp[i][i+k-1], x+A)
        if Pmin[i-1] - 1 >= i+k:
            dp[i+1][i+k] = min(dp[i+1][i+k], x)
        else:
            dp[i+1][i+k] = min(dp[i+1][i+k], x+B)
print(min([dp[i][i] for i in range(1, N+1)]))

Submission status: Wrong Answer

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 + n, INF)
            break
print(mf.max_flow(0, t))

Submission status: Wrong Answer

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)
        if l + 1 == r:
            mf.add_link(r, l + n, INF)
            break
print(mf.max_flow(0, t))

Submission status: Wrong Answer

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)
        if l + 1 == r:
            mf.add_link(r, l, INF)
            break
print(mf.max_flow(0, t))

Submission status: Wrong Answer

Solution code:
N, A, B = map(int, input().split())
P = list(map(int, input().split()))
Pmin = [None]*N
Pmax = [None]*N
for i, p in enumerate(P):
    k = 10000
    for pj in P[:i]:
        if pj > p:
            k = min(k, pj)
    Pmin[p-1] = k

for i, p in enumerate(P):
    k = -1
    for pj in P[:i:-1]:
        if pj < p:
            k = max(k, pj)
    Pmax[p-1] = k
dp = [[10**15]*(N+2) for _ in range(N+2)]
dp[1][N] = 0
for k in range(N-1, -1, -1):
    for i in range(1, N - k + 1):
        x = dp[i][i+k]
        if Pmax[i+k-1] + 1 <= i:
            dp[i][i+k-1] = min(dp[i][i+k-1], x)
        else:
            dp[i][i+k-1] = min(dp[i][i+k-1], x+A)
        if Pmin[i-1] - 1 >= i+k:
            dp[i+1][i+k] = min(dp[i+1][i+k], x)
        else:
            dp[i+1][i+k] = min(dp[i+1][i+k], x+B)
print(min([dp[i][i] for i in range(1, N+1)]))

Submission status: Wrong Answer

Solution code:
N, A, B = map(int, input().split())
P = list(map(int, input().split()))
Pmin = [None]*N
Pmax = [None]*N
for i, p in enumerate(P):
    k = 10000
    for pj in P[:i]:
        if pj > p:
            k = min(k, pj)
    Pmin[p-1] = k

for i, p in enumerate(P):
    k = -1
    for pj in P[:i:-1]:
        if pj < p:
            k = max(k, pj)
    Pmax[p-1] = k
dp = [[10**7]*(N+2) for _ in range(N+2)]
dp[1][N] = 0
for k in range(N-1, -1, -1):
    for i in range(1, N - k + 1):
        x = dp[i][i+k]
        if Pmax[i+k-1] + 1 <= i:
            dp[i][i+k-1] = min(dp[i][i+k-1], x)
        else:
            dp[i][i+k-1] = min(dp[i][i+k-1], x+A)
        if Pmin[i-1] - 1 >= i+k:
            dp[i+1][i+k] = min(dp[i+1][i+k], x)
        else:
            dp[i+1][i+k] = min(dp[i+1][i+k], x+B)
print(min([dp[i][i] for i in range(1, N+1)]))

Submission status: Time Limit Exceeded

Solution code:
n, a, b = map(int, input().split())
p = list(map(int, input().split()))
q = [0] * n
for i, x in enumerate(p):
    q[x - 1] = i
dp = [[0] * (n + 1) for _ in range(n + 1)]
mi = [[float('inf')] * (n + 1) for _ in range(n + 1)]
ma = [[0] * (n + 1) for _ in range(n + 1)]
for i in range(n + 1):
    for j in range(i + 1, n + 1):
        mi[i][j] = min(mi[i][j - 1], q[j - 1])
        ma[i][j] = max(ma[i][j - 1], q[j - 1])
for i in range(1, n + 1):
    for j in range(i + 1):
        k = i - j
        s, t = 1, 1
        if j > 0 and j == p[mi[j - 1][n - k]]:
            s = 0
        if k > 0 and n - k + 1 == p[ma[j][n - k + 1]]:
            t = 0
        if j == 0:
            dp[j][k] = dp[j][k - 1] + a * t
        elif k == 0:
            dp[j][k] = dp[j - 1][k] + b * s
        else:
            dp[j][k] = min(dp[j - 1][k] + b * s, dp[j][k - 1] + a * t)
ans = float('inf')
for i in range(n + 1):
    ans = min(ans, dp[i][n - i])
print(ans)