Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

NKBUS - Bus

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/nkbus


Một xe buýt của công ty có nhiệm vụ đón nhân viên đến trụ sở làm việc. Trên hành trình, xe buýt sẽ tiếp nhận nhân viên đứng chờ ở các điểm hẹn nếu như xe còn chỗ trống. Xe buýt có thể đỗ lại để chờ những công nhân chưa kịp đến điểm hẹn.

Cho biết thời điểm mà mỗi nhân viên đến điểm hẹn của mình và thời điểm qua mỗi điểm hẹn của xe buýt. Giả thiết rằng xe buýt đến điểm hẹn đầu tiên tại thời điểm 0 và thời gian xếp khách lên xe được bằng 0.

Xe buýt cần phải chở một số lượng nhiều nhất các nhân viên có thể được đến trụ sở. Hãy xác định khoảng thời gian ngắn nhất để xe buýt thực hiện công việc.

Dữ liệu vào

Dòng đầu tiên chứa 2 số nguyên dương n, m theo thứ tự là số điểm hẹn và số chỗ ngồi của xe buýt

Dòng thứ i trong số n dòng tiếp theo chứa số nguyên ti là thời gian cần thiết để xe buýt di chuyển từ điểm hẹn thứ i đến điểm hẹn thứ i+1 (điểm hẹn thứ n+1 sẽ là trụ sở làm việc của công ty) và số nguyên k là số lượng nhân viên đến điểm hẹn i, tiếp theo k số nguyên là các thời điểm đến điểm hẹn của k nhân viên.

Kết qủa

Gồm một dòng duy nhất, là thời gian ngắn nhất tìm được.

Giới hạn

1 ≤ n ≤ 200000, 1 ≤ m ≤ 20000

Tổng số nhân viên không vượt quá 200000.

Kết quả không vượt quá 231-1.

Ví dụ

Dữ liệu mẫu
3 2
3 2 4 3
1 3 6 3 7
5 1 5

Kết qủa
10

Giải thích: Trên đường đến công ty có 3 trạm xe buýt. Từ trạm 1 đến trạm 2, trạm 2 đến trạm 3, và từ trạm 3 đến công ty lần lượt mất 3, 1 và 5 đơn vị thời gian. Xe buýt có thể đi như sau: đến thẳng trạm 2, đón người thứ 2, đến trạm 3, chờ 1 đơn vị thời gian để đón người duy nhất ở trạm này, và cuối cùng đến công ty. Tổng cộng xe buýt đi mất 3 + 1 + 1 + 5 = 10 đơn vị thời gian.


Được gửi lên bởi:Jimmy
Ngày:2007-11-30
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ERL GOSU JS-RHINO NODEJS PERL6 PYPY RUST SED VB.NET
Nguồn bài:Adapted from Ukrainian OI 2000

hide comments
2021-11-04 08:07:18
4 3 4 1 1 1 3 2 1 2 2 2 3 2 4 3 2 3 3
8 5 11 1 3 1 5 2 2 2 3 2 5 2 8 3 4 3 5 3 6 3 7 4 3 4 6 5 1 5 6 6 1 6 2 6 4 6 5 7 2 7 5 7 7 7 8
25 18 157 15 15 15 16 20 20 20 22 20 24 20 25 7 15 7 17 2 8 2 9 8 20 8 23 24 24 24 25 21 15 21 16 21 20 21 21 22 13 22 16 14 12 14 14 21 4 21 6 1 21 1 24 12 17 12 18 6 13 6 15 13 14 13 17 9 15 9 17 11 1 11 2 1 6 1 7 17 9 17 11 6 7 6 10 20 4 20 7 20 15 20 16 18 16 18 19 22 9 22 10 18 3 18 4 2 16 2 19 14 21 14 23 11 9 11 11 9 6 9 7 10 20 10 23 8 4 8 5 18 20 18 23 13 23 13 25 22 5 22 7 8 9 8 10 14 6 14 7 17 2 17 3 15 1 15 2 9 19 9 21 16 22 16 25 12 5 12 6 13 6 13 9 20 10 20 11 4 15 4 17 19 17 19 18 10 13 10 14 3 7 3 8 5 10 5 13 12 22 12 24 10 5 10 7 2 4 2 6 1 13 1 14 5 15 5 18 24 20 24 23 9 11 9 14 12 12 12 13 14 17 14 20 5 21 5 24 23 22 23 24 19 5 19 7 23 4 23 7 3 19 3 22 8 15 8 18 24 8 24 9 3 16 3 18 15 18 15 20 2 13 2 14 20 18 20 19 16 14 16 17 17 16 17 18 2 20 2 22 11 4 11 7 11 15 11 16 16 10 16 13 23 1 23 2 10 11 10 12 3 23 3 25 24 10 24 11 6 24 6 25 10 8 10 9 3 11 3 12 7 22 7 25 23 10 23 11 5 5 5 6 15 24 15 25 6 18 6 20 11 20 11 23 22 18 22 20 15 21 15 22 6 22 6 23 10 24 10 25 21 23 21 24 14 24 14 25 8 11 8 12 19 12 19 14 1 2 1 4 3 3 3 4 18 8 18 11 23 14 23 17 13 4 13 5 17 4 17 6 4 24 4 25 9 2 9 5 21 1 21 3 6 2 6 5 16 1 16 2 15 5 15 8 15 3 15 4 19 9 19 11 24 1 24 4 7 8 7 10 19 1 19 2 17 19 17 22 4 4 4 5 5 1 5 3 9 22 9 23 7 18 7 21 20 1 20 3 1 18 1 20 12 10 12 11 22 23 22 25 7 13 7 14 4 21 4 23 17 7 17 8 17 12 17 14 11 12 11 14 10 16 10 19 21 17 21 19 18 6 18 7 21 10 21 12 16 20 16 21 10 1 10 3 11 17 11 19 12 14 12 16 7 3 7 6 18 12 18 13 17 24 17 25 23 12 23 13 19 24 19 25 4 7 4 9 3 1 3 2 24 17 24 18 8 1 8 3 19 21 19 22 11 24 11 25 4 10 4 12 7 1 7 2 13 10 13 13 12 1 12 2 16 6 16 9 18 14 18 15 2 23 2 25 15 11 15 12 3 14 3 15 24 14 24 16 14 1 14 2
35 12 285 4 29 4 31 18 22 18 23 23 33 23 35 9 2 9 3 3 8 3 9 31 33 31 35 23 11 23 14 21 9 21 11 10 18 10 19 18 30 18 31 3 22 3 25 29 3 29 4 6 30 6 32 14 22 14 24 21 33 21 34 28 16 28 18 32 18 32 21 1 24 1 27 11 26 11 29 21 17 21 20 9 33 9 35 26 30 26 32 18 32 18 33 20 17 20 18 25 5 25 6 15 17 15 20 32 34 32 35 7 21 7 24 29 16 29 18 30 14 30 16 18 8 18 9 27 25 27 28 27 15 27 18 22 7 22 9 19 30 19 32 16 20 16 23 7 5 7 8 5 11 5 13 15 10 15 12 3 28 3 29 19 8 19 10 20 31 20 32 24 11 24 14 23 16 23 17 33 10 33 11 2 3 2 4 10 32 10 34 2 14 2 15 34 5 34 7 8 10 8 12 17 33 17 35 5 28 5 30 8 13 8 16 25 18 25 19 6 10 6 11 30 22 30 24 9 31 9 32 20 5 20 6 15 31 15 33 30 10 30 13 4 2 4 4 1 18 1 20 25 34 25 35 33 7 33 8 9 22 9 23 30 33 30 34 18 2 18 4 25 24 25 27 30 26 30 28 13 31 13 34 12 27 12 28 14 4 14 7 6 7 6 9 17 11 17 13 6 17 6 19 18 15 18 17 21 12 21 15 3 12 3 13 15 1 15 3 19 18 19 21 26 22 26 25 10 7 10 8 12 4 12 5 20 8 20 9 4 11 4 13 17 2 17 3 4 34 4 35 2 28 2 29 18 25 18 28 1 29 1 31 11 7 11 10 29 28 29 30 23 21 23 23 31 15 31 17 4 16 4 18 33 12 33 13 32 14 32 15 27 4 27 7 29 33 29 34 26 1 26 2 27 32 27 35 31 5 31 8 29 21 29 24 29 11 29 12 33 21 33 23 16 30 16 33 5 5 5 6 7 16 7 18 5 3 5 4 33 31 33 33 23 4 23 7 11 21 11 23 17 20 17 21 19 23 19 26 31 25 31 28 17 24 17 26 17 14 17 15 20 1 20 2 5 23 5 25 15 15 15 16 8 19 8 22 20 28 20 30 24 27 24 28 18 12 18 13 28 10 28 12 6 34 6 35 24 20 24 23 28 22 28 25 21 1 21 3 9 4 9 5 22 15 22 18 31 20 31 23 22 19 22 22 12 33 12 35 33 34 33 35 1 34 1 35 27 9 27 11 10 9 10 10 5 34 5 35 26 4 26 7 6 12 6 13 24 6 24 8 4 22 4 25 7 13 7 14 9 11 9 13 20 25 20 27 26 11 26 13 17 17 17 19 7 26 7 29 30 1 30 4 25 8 25 11 24 31 24 33 12 18 12 19 24 15 24 16 14 26 14 27 23 24 23 26 22 31 22 33 25 12 25 14 13 21 13 23 24 9 24 10 33 25 33 26 16 8 16 9 11 14 11 15 32 8 32 9 6 21 6 22 22 28 22 29 25 1 25 3 31 11 31 14 21 22 21 25 12 14 12 16 34 14 34 17 2 16 2 19 25 20 25 23 14 16 14 19 13 28 13 30 34 32 34 33 1 1 1 3 34 27 34 29 10 3 10 4 26 20 26 21 32 5 32 7 32 29 32 32 14 10 14 12 28 5 28 7 8 33 8 35 2 20 2 23 3 18 3 21 23 1 23 2 17 4 17 7 13 24 13 26 6 24 6 26 7 30 7 31 16 26 16 29 7 32 7 35 21 29 21 32 29 25 29 27 12 21 12 23 19 12 19 15 16 3 16 4 30 17 30 19 2 9 2 10 32 2 32 4 20 20 20 21 11 1 11 3 13 1 13 2 19 27 19 28 20 10 20 11 24 1 24 3 26 16 26 18 28 27 28 30 13 18 13 19 10 21 10 23 2 1 2 2 8 3 8 5 11 34 11 35 10 11 10 12 26 14 26 15 1 16 1 17 9 25 9 26 7 9 7 12 33 2 33 3 14 28 14 30 12 12 12 13 3 16 3 17 16 1 16 2 5 26 5 27 13 5 13 6 1 9 1 12 27 21 27 22 32 22 32 23 27 1 27 3 12 10 12 11 19 34 19 35 1 22 1 23 8 23 8 25 13 15 13 17 4 19 4 21 12 1 12 2 34 34 34 35 13 9 13 12 2 34 2 35 1 13 1 15 17 27 17 28 10 25 10 27 34 22 34 24 22 4 22 6 15 34 15 35 32 11 32 12 25 29 25 31 16 34 16 35 10 28 10 29 16 15 16 18 28 34 28 35 1 7 1 8 14 32 14 35 8 26 8 28 12 7 12 9 1 4 1 6 26 27 26 28 13 3 13 4 5 17 5 18 9 14 9 17 22 25 22 27 6 1 6 2 24 24 24 26 2 5 2 7 2 30 2 32 8 29 8 31 23 29 23 31 20 13 20 14 19 2 19 5 32 24 32 27 33 17 33 19 15 24 15 27 28 19 28 20 34 3 34 4 29 13 29 14 20 34 20 35 11 30 11 33 30 29 30 31 11 5 11 6 34 19 34 21 14 1 14 3 14 8 14 9 28 13 28 14
2021-11-04 04:29:52
35 55
SEESEESSEBESBSBBBESEEESBESSBSBESSSSBBESEBEESBBSBBSESEEB
ESETESBSYEESEESEBESEEBEEBSBBSBESSESSEESBSBSSEEEBESEESBS
SSEESEESESEESBSSEEEESEEEEESEBSBESSSBEBSESSBEESESSSSESSE
SBSSESESEBSSBSESBBEBSEESESEEEBSESBBSSBSESSBSSEEESSSSESS
SBSSESEEESSEEEESEESBEBSESESEBSSSESEEESSEEEESBSSESEBSBEE
SEEBEEESSSBSEBEBSBSBSEBSBSEEBBSBBSESSSEEESESEEBSESSEEBE
SEEESESESBBEEBEEBSEESESEEESEESEEBEEEEBSSSSSSESSSEEEBEEE
ESSSSBEESBSESSEBEBESESBESSBEBEBEEBEBESSSBSSESEEEEBEBSEE
SSBEBEBBSSESEBSBESSEBEBSBSBEEESESEEBBSSBSSSBSSSESESEEES
SESBEBBSEBSBSSSBBEESESEESEBEEEEBSSESSBSESBESBSSSEESSEEE
EESESSEESEBSSEESBEEESBEESESSEBESEESESESEEEBSEESEBSSSEBS
ESSBEESBEESBSEESSBEEBBSBSBSBESEESBSBSSEBSSSSSSSESESEEES
SSSESEEESEESEEEEESEEEESBBEEBSSBSESBEESSEESSESSESBSBEBSS
BEBBESSSESEBBBSSESEBBEBSEBSEEBSBSESEEESSSEEBSSSBEESSEES
EESSBESSBBBSSSEEBESSSSSSBSEESESEEEBSESEEEESSBESSEESEBEB
SSBBESBEEBBBSSEESESEESBBBSSEBSSESSSEESBEBEEBSESEEEBEEEE
SSSEBBEEESEESBEBSSEESSBBBSSSESSEEBSEEEESSSESSSSBSSSEESS
ESBBBESSESEBBBSEEESSSSSSBSEEEBSESSBBESSSSESEESESEEESSSS
ESSSSSEESBSBEEESSEEBSEESSSSESSSSEESBSSSSEESBEEEEEESSEBE
EEEESBBSBESESEEESEBSBSEEBSEEEESSESESBESBESSSSBESBSESSSB
BBEBEEBSSSSSESSBESESEEEESBBBBEBBBSESEBSSSEEBBBEEEBEBESB
SBESESSBSBESESBESEEESEESBSBSEEESESSESBSBSESESBSBESSSEEB
SEEESEBBSEESSSBSBSSSSSEEESESBESEEESEBEBSBEESESEESSSEEES
EEEEEEBSBBEBSSEESEBEBSSBBESBBSSEESEEEBEEBSESESSSEESEEES
BBSSSSSESSSESBBESSSESSSSSESBESSSSBSSESSSBBSESEBBSBESSEE
SSEESSSBSESSSEEBSSBSBSSBEBSESSSSESSSESESEEESEESEBSESESS
SEESSEEBSBSEEBSBSSSSSEEEESESSSBEESBSSESSEEBBEBSSESEESSE
EESSEBBSESSBESSESESSSSSSSEESSSESESSESBSBBSSESEBSSSSEESS
EEBSBESSSESSEBEBSEBSBSSEEEEESSEBESSEEBESESESSBEEBSEBBBS
SESEESESESESBSEESSBSSEBSBSEEESEESESSEBBSBSEBSSSSSESBESB
EBBBEEBSEBBESBSSESEEEBSSESBSSEBESBSEEESSEESEESEEEBESBSB
BBESSEESEBSEESBSSBESSBSESEEESEESEEBSSESSSSSSSSSSESEESSE
SEESBSEEESEEESSEBSEBSSEESSEEBEBSBBSBSEESESESEBEEEBSSBBS
SSBSSSSSEESSSESEEEBBSSBSSBESSBESSSSBEBSSBSEEESEEBSESBSS
SBSSESBSEEBSESSSSSSSSBSEBBEEBSEEESBSEBEBBSSSSEEEBEEESSS
2021-11-04 04:29:25
15 15
YEEEEEEEEEEEEEE
EEBBEEBESEEESEE
BEEEEESESEEESBB
EEESEESSEEESEEE
EBBEEESBBBBBSEE
EEEBESEEESEEEEE
EESESEEEEEESEEE
BESEEEBEBEEEBEE
ESEEEBEESEEEBBE
SEEEEESSSEEEBEE
EESSESEEESEEEBS
EEEESSSESEEEBES
EEESEEESSSEEEEE
BEEEESBEEEESEBE
EEEBEEESEEEEEET
30 20
SYESSESEEEEBBSEBSBSS
SEEEEBESSSEEEBBSEEES
SSBBEEEESBESSEEESESE
SESBSEEBBBEBSBESSSBE
EBSSSEBSBBBSEEBSSSES
SESEESBSBEBESBBEEEES
ESSSBBESSEESSSSEESEB
SEESSBESSSSSEEESSEES
SESSSSSSESBSEBSSSSES
ESEESESEEEESBBEBBSSS
BBBEEEEBEEEBESBSBEES
EEEESSSESEESBSSBBEEE
SEEBSEBEBBSSSSSSEBSS
SBBBSEEEBESEBSBEBBES
BBESSSSEBBSEBSEEBBEE
ESBSEEEBBSSESESSEBSE
BBBSESSBBEESESBBSSBS
EEBSESSEEEBSBSSSBBES
SSSESSEEESSSSEEEBESE
EEBSBBSESESEEEESEBEE
BSEBESSESBEESSESSBES
SEBBBESEBSEESESESBSE
SSEESEBSSESBSESSBEEE
EBESESSSSESEEEEBSSSE
EEESBEBBBBBSSSSSSEEB
SBSEESEEESSSEESBESEB
SBBBEEEEBSESESEEEBSS
BBESEBSBSSESSBBBBBES
EESSEEEEEESSESSBSESB
BSESSEEBSESSSTSSBBSE
2021-11-04 04:28:57
3 4
YBEB
EERE
SSTE
3 4
YBEB
EERE
SSTS
3 4
YESS
EEEE
ESET
3 4
YESS
EEEE
ESBT
8 8
EESEEEEE
YBSEESEE
EEEESESE
ESEEEEES
ESBESEEE
ESSEEBBE
EEEEBBSE
EEBSEETS
2021-11-03 09:32:34
4 3 4 1 1 1 3 2 1 2 2 2 3 2 4 3 2 3 3
8 5 11 1 3 1 5 2 2 2 3 2 5 2 8 3 4 3 5 3 6 3 7 4 3 4 6 5 1 5 6 6 1 6 2 6 4 6 5 7 2 7 5 7 7 7 8
2021-08-21 03:07:06
nxhieu Hai Phong vo doi


Last edit: 2021-08-21 03:10:19
2021-08-21 03:07:05


nxhieu Hai Phong vo doi

Last edit: 2021-08-21 03:10:32
2021-05-27 18:02:15
Tham khảo: https://vnspoj.github.io/problems/NKBUS
2019-05-26 17:14:56
bài này mảng phải 250000 mới full
2019-03-20 10:09:56
Bai nay rat hay

Last edit: 2019-03-20 10:10:26
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.