a250. 202111_3. 生產線

Content

有 $n$ 台機器排成一直線, 每一個機器都有一個數值 $t_i$, 代表該台機器要產出一單位的資料需要 $t_i$ 單位的時間
接下來有 $m$ 個工作要完成, 每一個工作都需要位置在 $[l_i, r_i]$ 的機器各生產出 $w_i$ 單位資料
現在你可以調換 $n$ 台機器的順序, 目標是使得這 $m$ 個工作做完的總時間要最小

Input

先輸入兩個正整數 $n$ 和 $m$ 代表有 $n$ 台機器和 $m$ 個工作
接下來有 $m$ 行, 每行有三個正整數 $l_i$, $r_i$ 和 $w_i$ 代表第 $i$ 個工作需要編號從 $l_i$ 到 $r_i$ 的機器完成, 並且需要各產生出 $w_i$ 單位的資料

最後一行包含 $n$ 個正整數 $t_1,t_2,⋯t_n$

數字範圍

$1 \leq n, m \leq 200000$
$1 \leq w_i \leq 100$
$1 \leq t_i \leq 100$
$1 \leq l_i \leq r_i \leq n$

子題配分

(30%): $1 \leq n, m \leq 100, w_i = 1$
(30%): $w_i = 1$
(40%): 無額外限制

Output

輸出最小的總花費時間

Sample Input #1

5 1
2 4 1
1 2 3 4 5

Sample Output #1

Sample Input #2

10 3
2 5 6
3 6 4
7 8 1
1 2 3 4 5 6 7 8 9 10

Sample Output #2

測資資訊：

記憶體限制： 512 MB
公開測資點#0 (5%): 3.0s , <1K
公開測資點#1 (5%): 3.0s , <1K
公開測資點#2 (5%): 3.0s , <1M
公開測資點#3 (5%): 3.0s , <1M
公開測資點#4 (5%): 3.0s , <1M
公開測資點#5 (5%): 3.0s , <1M
公開測資點#6 (5%): 3.0s , <10M
公開測資點#7 (5%): 3.0s , <10M
公開測資點#8 (5%): 3.0s , <10M
公開測資點#9 (5%): 3.0s , <10M
公開測資點#10 (5%): 3.0s , <10M
公開測資點#11 (5%): 3.0s , <10M
公開測資點#12 (5%): 3.0s , <10M
公開測資點#13 (5%): 3.0s , <10M
公開測資點#14 (5%): 3.0s , <10M
公開測資點#15 (5%): 3.0s , <10M
公開測資點#16 (5%): 3.0s , <10M
公開測資點#17 (5%): 3.0s , <10M
公開測資點#18 (5%): 3.0s , <10M
公開測資點#19 (5%): 3.0s , <10M

Hint ：

Tags:

APCS

出處:

2021年11月 APCS 演算法海牛 [管理者： zero(管理員) ]

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