g597.
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], \cdots 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
6
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
117
測資資訊：
記憶體限制：
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
公開 測資點#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 ：
| ID | User | Problem | Subject | Hit | Post Date |
| 33704 |
|
g597 | 17 | 2023-01-24 21:36 | |
| 31590 |
|
g597 | 294 | 2022-08-08 23:09 | |
| 28267 |
|
g597 | 728 | 2021-11-23 16:18 | |
| 28073 |
|
g597 | 608 | 2021-11-12 20:22 | |
| 28048 | fire5386(Penguin07) | g597 | 910 | 2021-11-11 22:30 |