Finally, factoring in reliability WEIGHTS per sensor, Sabbir wants the increasing subsequence that maximizes (GCD of readings) × (total reliability weight). Read N integers, each also with a weight w_i. Among all strictly increasing subsequences, find the one that MAXIMIZES (GCD of chosen elements) × (sum of their weights). Print this maximum value. This combines the divisor-DP idea with an additional DP dimension for weight — think carefully about state design before coding.
Input
Line1: N. Line2: N integers (values). Line3: N integers (weights).
Output
The maximum achievable (GCD × weight-sum).
Constraints
1 ≤ N ≤ 2000, 1 ≤ a_i, w_i ≤ 2000
Sample Input
4 2 4 8 3 1 1 1 1
Sample Output
2*3=6
main.c
Loading editor…
Write C, then Run (custom I/O) or Submit (sample tests). ⌘/Ctrl+Enter submits.