2285 . 花花世界
TopCoder
Tags
Description
花花世界是一條一維的數線，在第 $0$ 天的時候，你在 $a_0$ 的位置種了一朵「花花度」是 $0$ 的花。
在接下來的 $n$ 天，每天都要種一朵新的花，種花方式如下:
花花世界有一個神奇常數 $k$ ($1 \leq k \leq n$)，後面會再說明其用意
對於第 $i$ 天($1 \leq i \leq n$)，會有一個 $b_i$ ($0 \leq b_i < i$)、要種花的位置 $a_i$ 和當天陽光強度 $m_i$。你要去採之前的某一天 $j$ ($0 \leq j < i$) 種的花產生的種子，而 $j$ 必須在 $[b_i - k + 1, b_i]$ 內。採完種子後你要在 $a_i$ 的位置種下花，但是在搬運種子時，會因為太陽照射的關係而發生基因突變。每往右走一單位距離，種子種出來的花的「花花度」就會增加 $m_i$，每往左走一單位則會減少 $m_i$，而種花的時候也會讓「花花度」增加 $m_i$。所以如果在第 $i$ 天要用第 $j$ 天的花的種子，那麼 $flower_i = flower_j + (a_i - a_j + 1) * m_i$，其中$flower_{x}$表示第 $x$ 天種出來的花的「花花度」($0 \leq x \leq n$)。
你要最大化 $\sum_{i = 0} ^ {n} flower_i$，請輸出其最大值 模 $1020050909$
Input Format
第一行有兩個整數 $n, k$，意義如題目所述。
第二行有 $n+1$ 個整數 $a_0, a_1, \cdots, a_n$
第三行有 $n$ 個整數 $b_1, b_2, \cdots b_n$
第四行有 $n$ 個整數 $m_1, m_2, \cdots m_n$
對於所有測資：
$1 \leq k \leq n \leq 10 ^ 6$
$0 \leq b_i < i, \forall i \in [1, n]$
$0 \leq a_i \leq 10 ^ 6, \forall i \in [0, n]$
$0 \leq m_i \leq 10 ^ 6, \forall i \in [1, n]$
輸入皆為非負整數
Output Format
輸出一個非負整數，為 $\sum_{i = 0} ^ {n} flower_i$ 的最大值模 $1020050909$
Sample Input 1
0 0 0 0 0 0
0 1 0 3 3
3 5 2 4 6
Sample Output 1
Sample Input 2
4 2 8 3 9 1 5 2
0 1 2 1 3 4 6
5 0 8 2 4 9 7
Sample Output 2
Hints
Problem Source
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0~3 | $\forall 0 \leq i \leq n, a_i = 0, k \leq 10$ | 3 |
| 2 | 4~7 | $\forall 0 \leq i \leq n, a_i = 0, \forall 1 \leq i \leq n, b_i = i - 1$ | 15 |
| 3 | 0~11 | $\forall 0 \leq i \leq n, a_i = 0$ | 20 |
| 4 | 12~15 | $n \leq 10 ^ 5$ | 36 |
| 5 | 0~22 | 無其他限制 | 26 |