[Compound] NKBUS
Threads: http://vn.spoj.com/problems/NKBUS/
A bus company's mission to welcome staff office. On the journey, Buses will receive staff waiting at the rendezvous if space is still available vehicles. Buses can park back to the workers barely wait to rendezvous.
Indicate the time that each employee to their rendezvous point and time of each meeting point of a bus. Assuming that the bus to the first rendezvous in time 0 and time is placed on the bus by 0.
Buses need to carry a number of most employees can be to headquarters. Please identify the shortest amount of time to perform the bus.
Data on
The first line contains 2 positive integer n, m is the order of the venue and the number of seats of the bus
Ith line of the next line contains n integers ti is the time required to move the bus from venue to venue ith th i 1 (rendezvous n 1 will be the office of the company) and the integer k is the number of employees to rendezvous i, next integer k is the time to rendezvous k staff.
The results
Consists of a single line, the shortest time to find.
Limit
1 ≤ n ≤ 200000, 1 ≤ m ≤ 20000
Total number of employees does not exceed 200000.
The results did not exceed 231-1.
Example
Data Modeling
3 2
3 2 4 3
1 3 6 3 7
5 1 5
The results
10
Explain: On the way to the company 3 Buses. From station 1 station 2, station 2 station 3, and from stations 3 Companies turn to take 3, 1 and 5 unit of time. Buses can go as follows: directly to stations 2, welcome party 2, station 3, await 1 unit time to pick only one in this station, and finally to the company. Total bus away 3 + 1 + 1 + 5 = 10 unit of time.
————————-
First noticed the car anyway and go from station 1 -> n + 1 Should the total of all time by the time the car goes from 1> n + 1.
Reviews found for each passenger station i may come before or after the bus station so i have an array W[] ie the time to wait for the bus station i and j of W[the] will by the time the visitor l (j guests at station i) i station except for time away from the bus station 1 to station i (If smaller 0 is regarded as = 0 ).
W Sort Ascending. After going ratings have w[the] the car waiting for the second time and also the time l vehicle l the seesaw
Finally, only the comparison of the passengers and m smaller one, we get the result added to the W[] in which.
Thank you, I have ac this article. Ask yourself
Last LQDBUS similar and just assign w[j] = Oo as j in the ith station to wait for the bus, must not?
But I do so that all that is only 10 point
I have not done all KQDBUS :D. To try it some day, now busy little :D. If there is something special about this article or articles on spoj hope you share. ^^
This paper you can cut algorithm AC binary?
This is also yet to learn their :D. If possible, please share with people offline.
His suggestion would be tight binary point “derived” by bus , due to the fact that passengers traveling to the venue will stand there and not going anywhere(Car starts so late that they have welcomed more passengers :D). And how much of my friends do not understand : in[in] Is time to wait in the car dock 1 any station to catch sl[in] person or not?(sl[in] the act of Independence was waiting at the station after waiting car w[in] at station).
So, I do not know how it does not. But then as you say, in[in] timeout is the ith (i was waiting at the station that).
However, because each station has many, the people at each station are counted by the variable i (ith the) so I put the w[the] (l the first timeout of the car – as well as the timeout 1 ith certain people in the dock).
You Quan dear, I would like to address to your email ko DC? Do I need your advice to help DC ko sir?
You send email: nguyenvanquan7826@gmail.com