TopCoder

Adrien Wu
$ \begin{align} AC \times 2^9 \\ \text{New TIOJ ?} \end{align} $

User's AC Ratio

46.2% (6/13)

Submission's AC Ratio

22.2% (16/72)

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

5 3
0 0 0 0 0 0
0 1 0 3 3
3 5 2 4 6

Sample Output 1

39

Sample Input 2

7 3
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

87

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

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 3000 524188 65536 1 3 5
1 3000 524188 65536 1 3 5
2 3000 524188 65536 1 3 5
3 3000 524188 65536 1 3 5
4 3000 524188 65536 2 3 5
5 3000 524188 65536 2 3 5
6 3000 524188 65536 2 3 5
7 3000 524188 65536 2 3 5
8 3000 524188 65536 3 5
9 3000 524188 65536 3 5
10 3000 524188 65536 3 5
11 3000 524188 65536 3 5
12 3000 524188 65536 4 5
13 3000 524188 65536 4 5
14 3000 524188 65536 4 5
15 3000 524188 65536 4 5
16 3000 524188 65536 5
17 3000 524188 65536 5
18 3000 524188 65536 5
19 3000 524188 65536 5
20 3000 524188 65536 5
21 3000 524188 65536 5
22 3000 524188 65536 5