Strange Set
Contest: Educational Codeforces Round 102 (Rated for Div. 2)
Difficulty rating: 2700
Tags: flows, math

Note that the memory limit is unusual.

You are given an integer $$$n$$$ and two sequences $$$a_1, a_2, \dots, a_n$$$ and $$$b_1, b_2, \dots, b_n$$$.

Let's call a set of integers $$$S$$$ such that $$$S \subseteq \{1, 2, 3, \dots, n\}$$$ strange, if, for every element $$$i$$$ of $$$S$$$, the following condition is met: for every $$$j \in [1, i - 1]$$$, if $$$a_j$$$ divides $$$a_i$$$, then $$$j$$$ is also included in $$$S$$$. An empty set is always strange.

The cost of the set $$$S$$$ is $$$\sum\limits_{i \in S} b_i$$$. You have to calculate the maximum possible cost of a strange set.

Input format:
The first line contains one integer $$$n$$$ ($$$1 \le n \le 3000$$$).

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 100$$$).

The third line contains $$$n$$$ integers $$$b_1, b_2, \dots, b_n$$$ ($$$-10^5 \le b_i \le 10^5$$$).

Output format:
Print one integer — the maximum cost of a strange set.

Constraints:
Time limit: 4.0 s
Memory limit: 32.0 MB

Note:
The strange set with the maximum cost in the first example is $$$\{1, 2, 4, 8, 9\}$$$.

The strange set with the maximum cost in the second example is empty.

Example input:
9
4 7 3 4 5 6 7 8 13
-2 3 -19 5 -6 7 -8 9 1

Example output:
16

Example input:
2
42 42
-37 13

Example output:
0

Editorial:
We will model the problem as the minimum cut in a flow network.
Build a network as follows: create a source node $$$s$$$, a sink node $$$t$$$, and a vertex for every number from $$$1$$$ to $$$n$$$. Let's say that we are going to find the minimum $$$s$$$-$$$t$$$ cut in this network, and the vertices belonging to the same cut part with $$$s$$$ represent the numbers that are taken into the answer.
Using the edges of the network, we should model these constraints:
1. taking an element $$$i$$$ that depends on another element $$$j$$$ should force us to take $$$j$$$ as well;
2. taking an element $$$i$$$ with $$$b_i > 0$$$ should add $$$b_i$$$ to our score;
3. taking an element $$$i$$$ with $$$b_i < 0$$$ should subtract $$$|b_i|$$$ from our score.
Constraint $$$1$$$ can be modeled in the following way: for every pair $$$(i, j)$$$ such that element $$$i$$$ depends on element $$$j$$$ ($$$i > j$$$ and $$$a_i \bmod a_j = 0$$$), add a directed edge with infinite capacity from $$$i$$$ to $$$j$$$. That way, if $$$i$$$ is taken and $$$j$$$ is not, the value of the cut will be infinite because of this edge, and this cut cannot be minimum.
Constraint $$$2$$$ is modeled in the following way: for every $$$i$$$ such that $$$b_i > 0$$$, add a directed edge with capacity $$$b_i$$$ from $$$s$$$ to $$$i$$$. That way, if we don't take some element $$$i$$$ with $$$b_i > 0$$$ into the answer, $$$b_i$$$ is added to the value of the cut.
And for constraint $$$3$$$, for every $$$i$$$ such that $$$b_i < 0$$$, add a directed edge with capacity $$$|b_i|$$$ from $$$i$$$ to $$$t$$$. That way, if we take some element $$$i$$$ with $$$b_i < 0$$$, $$$|b_i|$$$ is added to the value of the cut.
It's now easy to see that the answer is $$$\sum\limits_{i = 1}^{n} \max(b_i, 0) - mincut$$$, since it is exactly the sum of elements that were taken (for positive elements, we add them all up and then subtract the ones that don't belong to the answer; for negative ones, we just subtract those which belong to the answer). To find a minimum cut, just run maximum flow in this network.
There's one caveat though. If, for example, all $$$a_i$$$ are equal (or many $$$a_i$$$ are divisible by many other values in $$$a$$$), this network can contain $$$O(n^2)$$$ edges. To reduce the number of edges, let's see that if for some index $$$i$$$ there exist two equal divisors of $$$a_i$$$ to the left of it (let's say that these divisors are $$$j$$$ and $$$k$$$: $$$j < k < i$$$; $$$a_i \bmod a_j = 0$$$; $$$a_j = a_k$$$), then we only need to add an edge from $$$i$$$ to $$$k$$$, because taking $$$k$$$ also should force taking $$$j$$$ into the answer. So, for every divisor of $$$a_i$$$, we are interested in only one closest occurrence of this divisor to the left, and we need to add a directed edge only to this occurrence, and ignore all other occurrences. That way, for every vertex $$$i$$$, we add at most $$$D(a_i)$$$ edges to other vertices (where $$$D(a_i)$$$ is the number of divisors of $$$a_i$$$).
It can be proven that any maximum flow algorithm that relies on augmenting paths will finish after $$$O(V)$$$ iterations in this network, so it won't work longer than $$$O(VE)$$$, and both $$$V$$$ and $$$E$$$ are proportional to $$$n$$$, so any maximum flow solution will run in $$$O(n^2)$$$.