i963.
疊疊杯子蛋糕 ꝏ Extreme
內容
原題：在聽了花花世界之後，小琳想要做杯子蛋糕給小艾吃，於是準備了 $n$ 個麵團，每個麵團有兩個值 $a_i$ 和 $b_i$。
想要將麵團分為若干個區間 $[l_1, r_1], [l_2, r_2],\dots,[l_k, r_k]$，每個麵團恰屬於一個區間，區間 $[l, r]$ 的好吃度 $D(l, r)$ 為 $\sum\limits_{i=l}^{r}(i-l+1)\times a_i+b_{l-1}\times\sum\limits_{i=l}^{r}a_i$ (定義 $b_0 = 0$)。
你想找出一種分法使得 $\sum\limits_{i = 1}^kD(l_i, r_i)$ 最大，且 $r_i - l_i + 1\leq K$，請輸出 $\sum\limits_{i = 1}^kD(l_i, r_i)$ 最大可以是多少。
輸入說明
第一行有兩個正整數 $n,K$，代表有 $n$ 個麵團，和每個杯子蛋糕最多只能由 $K$ 個麵團疊成。
第二行有 $n$ 個整數 $a_1\sim a_n$ 。
第三行有 $n$ 個整數 $b_1\sim b_n$ ，代表 $n$ 個麵團的美麗度。
- $1\leq K\leq n\leq 10^6$
- $-10^3\leq a_i\leq 10^3$
- $-10^9\leq b_i\leq 10^9$
輸出說明
輸出 $\sum\limits_{i = 1}^kD(l_i, r_i)$ 最大可以是多少。
範例輸入
#1
5 2 1 2 3 4 5 -1 -2 -3 -4 -5
範例輸出
#1
-9
範例輸入
#2
20 2 -391 784 884 -924 -365 -429 -379 988 445 -381 -464 -908 -173 -846 -912 -643 860 647 180 -181 958978129 78445833 991154106 831306943 -660088085 -9992717 874054816 34873121 954789447 -473259031 692625722 827418239 -868716573 -884911232 -436132937 -582959368 -896777725 -584065635 7739542 567437143
範例輸出
#2
3606574445933
測資資訊：
記憶體限制：
512
MB
不公開 測資點#0 (12%): 2.5s , <10M
不公開 測資點#1 (12%): 2.5s , <10M
不公開 測資點#2 (12%): 2.5s , <10M
不公開 測資點#3 (12%): 2.5s , <50M
不公開 測資點#4 (13%): 2.5s , <50M
不公開 測資點#5 (13%): 2.5s , <50M
不公開 測資點#6 (13%): 2.5s , <50M
不公開 測資點#7 (13%): 2.5s , <50M
不公開 測資點#0 (12%): 2.5s , <10M
不公開 測資點#1 (12%): 2.5s , <10M
不公開 測資點#2 (12%): 2.5s , <10M
不公開 測資點#3 (12%): 2.5s , <50M
不公開 測資點#4 (13%): 2.5s , <50M
不公開 測資點#5 (13%): 2.5s , <50M
不公開 測資點#6 (13%): 2.5s , <50M
不公開 測資點#7 (13%): 2.5s , <50M
提示 ：
$100\%：無特別限制$
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
|
沒有發現任何「解題報告」
|
|||||