i963: 疊疊杯子蛋糕 ꝏ Extreme
Tags : 動態凸包 斜率優化 李超線段樹
Accepted rate : 1人/1人 ( 100% ) [非即時]
評分方式:
Tolerant

最近更新 : 2022-10-14 15:50

Content

原題:在聽了花花世界之後,小琳想要做杯子蛋糕給小艾吃,於是準備了 $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)$ 最大可以是多少。

Input

第一行有兩個正整數 $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$
Output

輸出 $\sum\limits_{i = 1}^kD(l_i, r_i)$ 最大可以是多少。

Sample Input #1
5 2
1 2 3 4 5
-1 -2 -3 -4 -5
Sample Output #1
-9
Sample Input #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
Sample Output #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
Hint :

$100\%:無特別限制$

Tags:
動態凸包 斜率優化 李超線段樹
出處:
Caido [管理者: becaido(Caido) ]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」