Berserk And Fireball (Codeforces 1380D)
Tags: Greedy, two pointers

There are $$$n$$$ warriors in a row. The power of the $$$i$$$-th warrior is $$$a_i$$$. All powers are pairwise distinct.You have two types of spells which you may cast:   Fireball: you spend $$$x$$$ mana and destroy exactly $$$k$$$ consecutive warriors;  Berserk: you spend $$$y$$$ mana, choose two consecutive warriors, and the warrior with greater power destroys the warrior with smaller power. For example, let the powers of warriors be $$$[2, 3, 7, 8, 11, 5, 4]$$$, and $$$k = 3$$$. If you cast Berserk on warriors with powers $$$8$$$ and $$$11$$$, the resulting sequence of powers becomes $$$[2, 3, 7, 11, 5, 4]$$$. Then, for example, if you cast Fireball on consecutive warriors with powers $$$[7, 11, 5]$$$, the resulting sequence of powers becomes $$$[2, 3, 4]$$$.You want to turn the current sequence of warriors powers $$$a_1, a_2, \dots, a_n$$$ into $$$b_1, b_2, \dots, b_m$$$. Calculate the minimum amount of mana you need to spend on it.

Input: The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n, m \le 2 \cdot 10^5$$$) — the length of sequence $$$a$$$ and the length of sequence $$$b$$$ respectively.The second line contains three integers $$$x, k, y$$$ ($$$1 \le x, y, \le 10^9; 1 \le k \le n$$$) — the cost of fireball, the range of fireball and the cost of berserk respectively.The third line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le n$$$). It is guaranteed that all integers $$$a_i$$$ are pairwise distinct.The fourth line contains $$$m$$$ integers $$$b_1, b_2, \dots, b_m$$$ ($$$1 \le b_i \le n$$$). It is guaranteed that all integers $$$b_i$$$ are pairwise distinct.

Output: Print the minimum amount of mana for turning the sequnce $$$a_1, a_2, \dots, a_n$$$ into $$$b_1, b_2, \dots, b_m$$$, or $$$-1$$$ if it is impossible.


Sample Inputs:
5 2
5 2 3
3 1 4 5 2
3 5

4 4
5 1 4
4 3 1 2
2 4 3 1

4 4
2 1 11
1 3 2 4
1 3 2 4

Sample Outputs:
8

-1

0

Solution (Python):
from math import ceil
import os
import sys
from io import BytesIO, IOBase
BUFSIZE: int = 8192

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            (self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda : self.buffer.read().decode('ascii')
        self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
    """"""
    (sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop('end', '\n'))
    if kwargs.pop('flush', False):
        file.flush()
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
if __name__ == '__main__':
    pass

def inpi():
    return int(input())

def inpl():
    return list(map(int, input().split()))

def inps():
    s = input()
    return list(s[:len(s)])

def inpm():
    return map(int, input().split())

def inpst():
    return set(map(int, input().split()))

def solve():
    (n, m) = inpl()
    (x, k, y) = inpl()
    a = inpl()
    sa = set(a)
    b = inpl()
    sb = set(b)
    flag = False
    so_far = []
    l = 0
    max_sofar = -1
    ans = 0
    check = []
    for i in a:
        if i in sb:
            check.append(i)
            if flag:
                if len(so_far) == 0:
                    l = i
                    max_sofar = -1
                    continue
                r = i
                if x > k * y:
                    if max_sofar < l or max_sofar < r:
                        ans += len(so_far) * y
                    else:
                        ixat = len(so_far) // k
                        yagat = len(so_far) - k
                        ans += x + yagat * y
                        if ixat < 1:
                            print(-1)
                            return
                else:
                    ixat = len(so_far) // k
                    yagat = len(so_far) % k
                    ans += x * ixat + yagat * y
                    if max_sofar > l and max_sofar > r:
                        if ixat < 1:
                            print(-1)
                            return
                so_far = []
                l = r
                max_sofar = -1
                falg = False
            else:
                l = i
                max_sofar = -1
                sofar = []
                flag = True
        else:
            so_far.append(i)
            max_sofar = max(max_sofar, i)
            flag = True
    if check != b:
        print(-1)
        return
    if len(so_far) == 0:
        print(ans)
        return
    r = 0
    l = b[-1]
    if x > k * y:
        if max_sofar < l or max_sofar < r:
            ans += len(so_far) * y
        else:
            ixat = len(so_far) // k
            yagat = len(so_far) - k
            ans += x + yagat * y
            if ixat < 1:
                print(-1)
                return
    else:
        ixat = len(so_far) // k
        yagat = len(so_far) % k
        ans += x * ixat + yagat * y
        max_sofar = max(so_far)
        if max_sofar > l and max_sofar > r:
            if ixat < 1:
                print(-1)
                return
    so_far = []
    l = r
    max_sofar = -1
    falg = False
    print(ans)
''
t = 1
for _ in range(t):
    solve()

Solution (Python):
import sys
input = sys.stdin.readline

def readList():
    return list(map(int, input().split()))

def readInt():
    return int(input())

def readInts():
    return map(int, input().split())

def readStr():
    return input().strip()

def solve():
    (n, m) = readInts()
    (x, k, y) = readInts()
    (A, B) = (readList(), readList())
    A.append(0)
    B.append(0)
    (n, m) = (n + 1, m + 1)
    prev = v = -float('inf')
    j = cnt = ans = 0
    for i in range(n):
        if j < m and A[i] == B[j]:
            if not cnt:
                prev = A[i]
                v = -float('inf')
                j += 1
                continue
            if v < max(A[i], prev):
                ans += min(x * (cnt // k) + y * (cnt % k), cnt * y)
            elif cnt < k:
                return -1
            else:
                cnt -= k
                ans += x + min(x * (cnt // k) + y * (cnt % k), cnt * y)
            (prev, cnt, v) = (A[i], 0, -float('inf'))
            j += 1
        else:
            v = max(v, A[i])
            cnt += 1
    return ans if j == m else -1
print(solve())

Solution (Python):
from typing import *
from math import *
from functools import lru_cache
from queue import PriorityQueue, Queue
import sys

def I():
    return input()

def II():
    return int(input())

def MII():
    return map(int, input().split())

def LI():
    return list(input().split())

def LII():
    return list(map(int, input().split()))
(n, m) = MII()
(x, k, y) = MII()
a = LII()
b = LII()
segs = []
d1 = 0
l = 0
for i in range(n):
    if d1 < m and a[i] == b[d1]:
        if i >= l + 1:
            segs.append((b[d1 - (1 if d1 else 0)], l, i - 1, b[d1]))
        l = i + 1
        d1 += 1
if d1 != m:
    print(-1)
    exit(0)
if l <= n - 1:
    segs.append((b[d1 - 1 - (1 if d1 - 1 else 0)], l, n - 1, b[d1 - 1]))
res = 0
for (l, s, e, r) in segs:
    over = False
    mx = max(l, r)
    for i in range(s, e + 1):
        if a[i] > mx:
            over = True
            break
    if over:
        if e - s + 1 < k:
            print(-1)
            exit(0)
        d = e - s + 1 - k
        res += min(d // k * x + d % k * y, d * y) + x
    else:
        d = e - s + 1
        res += min(d // k * x + d % k * y, d * y)
print(res)