看著 2066 年 6 月 6 日 Automatic Investment 公司開發出來商品價格的預測系統「AI-666」，身為瘋狂科學家的小 Y 感到氣氣氣氣氣，所以他決定開發出一個新的系統，用來直接擾亂未來股市的股價波動，他將此系統命名為「AI-777」。商品交易的規則是這樣的：
1. 每天商品的價格都有可能不同，所以買家可以選擇一天買入商品，並在往後的另一天賣出該商品來透過價差獲利。
2. 由於法令的規定，在此期間內最多只能進行一次的交易(一次交易包含買賣各一次)。
AI-777 的使用方法如下：
1. 首先先將 AI-666 預測出來 n 天的商品價格(一個長度 n 的正整數序列)轉換成商品價差(一個長度 n − 1 的整數序列 d1 ∼ dn−1，也就是說，序
列中第 i 個數字，實際上會是第 i 天和第 i + 1 天的商品價差)。
2. 接著，AI-777 會根據現在的社會局勢生產出 k 個整數 x1 ∼ xk，得到這些數字之後，使用者就可以把轉換過後的序列中選擇出至多 k 個位置的
數字換成 AI-777 生產出來的數字(每個數字只能用一次，可以用任意順序使用，也可以用來修改任意位置的價差，而且可以不用用完)。在更改完
價差序列後，使用者可以把價差序列轉換回長度 n 的價格序列,並在未來籌畫策略進行交易。
小 Y 在搞定 AI-777 之後就已經精疲力盡了，所以他想請你幫他計算出，假設 AI-666 的價格預測是準確的，且 AI-777 也確實可以擾亂未來股市，那麼在預測到的那 n 天當中，進行一次交易最多可以賺到多少錢？請注意，在本題當中，AI-666 預測出來第一天的商品價格永遠為1015，在測資限制下，我們保證不會有價格低於零的情況。
輸入共有三行。
首行為三個非負整數 n, k (1 ≤ n ≤ 105， 0 ≤ k ≤ 100)，分別代表天數和 AI-777 生產出來的數字個數。
接下來一行 n − 1 個整數 d1 ∼ dn−1 ( |di| ≤ 109 ) ，其中 di 代表 AI-666 預測出來的商品價格中，第 i + 1 天的商品價格扣掉第 i 天的商品價格。
最後一行會有 k 個整數 x1 ∼ xk ( |xi| ≤ 109)，代表 AI-777 生產出來的 k 個數字。
以單獨一行輸出最大可能獲利，若無法獲利則應輸出 0。
#test input 1: 10 0 56 -38 -62 87 -44 2 -34 28 34 #test input 2: 10 2 56 -38 -62 87 -44 2 -34 28 34 20 -3
#test output 1: 87 #test output 2: 168
公開 測資點#0 (2%): 1.0s , <1M
公開 測資點#1 (2%): 1.0s , <10M
公開 測資點#2 (2%): 1.0s , <10M
公開 測資點#3 (2%): 1.0s , <1M
公開 測資點#4 (2%): 1.0s , <10M
公開 測資點#5 (2%): 1.0s , <1M
公開 測資點#6 (3%): 1.0s , <1M
公開 測資點#7 (1%): 1.0s , <1K
公開 測資點#8 (1%): 1.0s , <1K
公開 測資點#9 (1%): 1.0s , <1K
公開 測資點#10 (1%): 1.0s , <1K
公開 測資點#11 (1%): 1.0s , <1K
公開 測資點#12 (1%): 1.0s , <1M
公開 測資點#13 (1%): 1.0s , <10M
公開 測資點#14 (1%): 1.0s , <1M
公開 測資點#15 (2%): 1.0s , <10M
公開 測資點#16 (2%): 1.0s , <10M
公開 測資點#17 (2%): 1.0s , <10M
公開 測資點#18 (2%): 1.0s , <1M
公開 測資點#19 (2%): 1.0s , <1M
公開 測資點#20 (2%): 1.0s , <1M
公開 測資點#21 (2%): 1.0s , <1K
公開 測資點#22 (2%): 1.0s , <1K
公開 測資點#23 (2%): 1.0s , <1K
公開 測資點#24 (2%): 1.0s , <1M
公開 測資點#25 (2%): 1.0s , <1M
公開 測資點#26 (2%): 1.0s , <1M
公開 測資點#27 (2%): 1.0s , <1M
公開 測資點#28 (2%): 1.0s , <1M
公開 測資點#29 (2%): 1.0s , <10M
公開 測資點#30 (2%): 1.0s , <10M
公開 測資點#31 (2%): 1.0s , <1M
公開 測資點#32 (2%): 1.0s , <1M
公開 測資點#33 (2%): 1.0s , <1M
公開 測資點#34 (2%): 1.0s , <1M
公開 測資點#35 (2%): 1.0s , <1M
公開 測資點#36 (2%): 1.0s , <1M
公開 測資點#37 (2%): 1.0s , <10M
公開 測資點#38 (3%): 1.0s , <10M
公開 測資點#39 (3%): 1.0s , <1M
公開 測資點#40 (3%): 1.0s , <1M
公開 測資點#41 (1%): 1.0s , <1K
公開 測資點#42 (1%): 1.0s , <1K
公開 測資點#43 (1%): 1.0s , <1M
公開 測資點#44 (1%): 1.0s , <1M
公開 測資點#45 (1%): 1.0s , <1M
公開 測資點#46 (1%): 1.0s , <1M
公開 測資點#47 (1%): 1.0s , <1M
公開 測資點#48 (1%): 1.0s , <1M
公開 測資點#49 (1%): 1.0s , <10M
公開 測資點#50 (1%): 1.0s , <1M
公開 測資點#51 (1%): 1.0s , <1M
公開 測資點#52 (1%): 1.0s , <1M
公開 測資點#53 (1%): 1.0s , <1M
公開 測資點#54 (1%): 1.0s , <10M
公開 測資點#55 (1%): 1.0s , <1M
公開 測資點#56 (1%): 1.0s , <1M
公開 測資點#57 (1%): 1.0s , <1M
公開 測資點#58 (1%): 1.0s , <10M
公開 測資點#59 (1%): 1.0s , <1M
公開 測資點#60 (1%): 1.0s , <10M
公開 測資點#61 (1%): 1.0s , <10M
公開 測資點#62 (1%): 1.0s , <1M
dp, greedy, sortings (CF 2000)
15% 的測資滿足 k = 0
20% 的測資滿足 k = 1
43% 的測資滿足所有的 xi 都是相同的
22% 的測資無其他限制
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
| 158 | a267 | 5 | 2025-01-06 20:55 |