You are given two arrays, $a$ of length $n$, and $b$ of length $m$. You are also given for each element in $a$, the cost of removing it ($cost_i$).
The elements in $b$ are distinct, and initially, they form a subsequence of $a$. Find the minimum sum of costs possible such that $b$ remains a subsequence of $a$ after removing zero or more elements.
The first line of input contains 2 integers $n$ and $m$ ($1 \leq m \leq n \leq 10^6$).
The second line contains $n$ space-separated integers ($1 \leq a_i \leq n$), the elements of $a$.
The third line contains $n$ space-separated integers ($-10^6 \leq cost_i \leq 10^6$), the elements of $cost$.
The fourth line contains $m$ distinct integers ($1 \leq b_i \leq n$), the elements of $b$. It's guaranteed that $b$ is a subsequence of $a$.
Print a single integer with the answer to the problem.
An array $b$ is a subsequence of array $a$ if $b$ can be derived from $a$ by deleting zero or more elements from $a$, without changing the order of the remaining elements.
| Input | Output |
|---|---|
5 3 1 2 3 4 5 -5 -19 -1 0 3 2 4 5 Copy
|
-6 Copy
|
6 3 1 3 3 2 4 6 -1 -5 -10 4 -3 5 1 3 2 Copy
|
-13 Copy
|
It's obvious that we won't remove any element with a positive cost, so let's change these costs to zero. Now we want to erase all elements with a negative cost except for a subsequence of $b$ with the maximum cost, to find such a subsequence, we do dp.
Let $dp_i$ be the maximum cost for the array $b_1, b_2,...,b_i$ as a subsequence in $a$. Let's traverse $a$ index by index and each time update $dp$, if we are at index $i$ and $a_i$ is present in $b$ at index $j$, then we should update $dp_j$ with $\max(dp_j, dp_{j-1} + cost_i)$. The final answer will be the sum of all the negative costs - $dp[m]$.
package main
import (
"fmt"
"bufio"
"os"
)
var reader *bufio.Reader = bufio.NewReader(os.Stdin)
var writer *bufio.Writer = bufio.NewWriter(os.Stdout)
func scanf(f string, a ...interface{}) { fmt.Fscanf(reader, f, a...) }
func printf(f string, a ...interface{}) { fmt.Fprintf(writer, f, a...) }
const N = 1000000
var a, cst, b, ord [N + 1]int
var dp [N + 1]int64
func up(x *int64, y int64){
if (y > *x) { *x = y }
}
func main(){
defer writer.Flush()
var n, m int
scanf("%d%d\n", &n, &m)
for i := 1; i <= n; i++ { scanf("%d", &a[i]) }
scanf("\n")
var sm int64 = 0
for i := 1; i <= n; i++ {
scanf("%d", &cst[i])
if cst[i] > 0 { cst[i] = 0 } else { sm += int64(cst[i]) }
}
scanf("\n")
for i := 1; i <= m; i++ {
scanf("%d", &b[i])
ord[b[i]] = i;
dp[i] = int64(-1e18)
}
scanf("\n")
for i := 1; i <= n; i++{
if ord[a[i]] > 0 {
up(&dp[ord[a[i]]], dp[ord[a[i]] - 1] + int64(cst[i]))
}
}
printf("%d\n", sm - dp[m])
}