79. Simple DP Problem

0 Judge

Code: 0


Simple DP Problem

題目敘述

給定陣列 $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]$ 當答案

Sample Input

3
1 -2
-4 -5
2 -3

Sample Output

12

Sample Input

5
9 7
-10 2
-10 -7
4 9
4 0

Sample Output

149

Note

20% Credit for $N\leq 1000$

Hint

可以參考講義程式碼(講義有一部分有誤)

https://gist.github.com/rareone/aeb1d7ca0633d84aea6599a302cfb049


Judge Setting

run-time limit: 3500 ms
memory limit: 268435456 byte
測資數量: 7