0 Judge
Code: 0
給定陣列 $a = [a_0, a_1, \cdots, a_{n - 1}], b = [b_0, b_1, \cdots, b_{n - 1}]$，試處理 $$ dp[i] = \max_{0 \leq j < i} \{ a[i - 1] \times b[j] + dp[j] \}, i \in [1, n] $$
初始條件 $dp[0] = 0$，答案輸出 $dp[n]$
$$ 1 \leq n \leq 10^5 $$
$$ |a_i|, |b_i| \leq 10^6 $$
每筆測資只有一個輸入
第一行有一個數字 $n$
接著輸出 $n$ 行代表 $a_i, b_i$
輸出一個數字 $dp[n]$ 當答案
3
1 -2
-4 -5
2 -3125
9 7
-10 2
-10 -7
4 9
4 014920% Credit for $N\leq 1000$
可以參考講義程式碼（講義有一部分有誤）
https://gist.github.com/rareone/aeb1d7ca0633d84aea6599a302cfb049