a250. 202111_3. 生產線
Tags : APCS
Accepted rate : 5人/5人 ( 100% ) [非即時]
評分方式:
Tolerant

最近更新 : 2021-11-18 10:00

Content

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

Input

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

 最後一行包含 n 個正整數 t1,t2,tn

數字範圍

  • 1n,m200000
  • 1wi100
  • 1ti100
  • 1lirin

子題配分

  • (30%): 1n,m100,wi=1
  • (30%): wi=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
Hint :
Tags:
APCS
出處:
2021年11月APCS演算法海牛 [管理者: zero(管理員) ]


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