Nộp bài  Các bài nộp  Làm tốt nhất  Về danh sách bài 
TRAKA  TRAKA 
As mentioned before, there are N workers in Mirko's factory. They are manufacturing cars on a conveyor belt, in a pipeline fashion.
Workers are denoted by numbers 1 – leftmost, to N  rightmost. Each of the workers does his specific job and requires certain amount of time to complete it.
Production of a single car starts with worker #1 (Mirko). After he had finished with his part of the job, worker #2 takes over, after him #3... When worker #N finishes with his part, the car is finished.
Mirko and his workers have to produce M cars and they must produce them in order 1 to M.
For every worker i we know T[i]  time required for him to do his part of the job.
For every car j we know factor of assembly complexity F[j].
Time in minutes for worker i to finish his part of he job on the car j is computed as a product T[i]*F[j].
After some worker has finished working on a car, he has to give it to the next worker instantly, without any delay (weird company policy).
For that reason, the worker receiving the car has to be free (he must not be working on some other car). In order to fulfill this condition, Mirko has to choose a good timing to start building a new car. To be efficient, he’ll wait minimum number of minutes until he is certain that all of the conditions described are met.
Write a program which will, given worker times and factors of complexity for each car, compute total time required for producing all of the cars.
Input
First line of input contains spaceseparated positive integers N (1 ≤ N ≤ 100 000), number of workers, and M (1 ≤ M ≤ 100 000), number of cars.
ith of the following N lines contains worker time T[i] for the worker i.
jth of the following M lines contains factor of complexity F[j] for the car j.
These conditions hold: 1 ≤ T[i] ≤ 10 000, 1 ≤ F[j] ≤ 10 000.
Output
First and only line of output has to contain required number of minutes.
In test cases worth 40% of total points, N and M will be at most 1000.
Input:
3 3
2
1
1
2
1
1
Output:
11
Sample description: After four minutes, first worker finishes working on the first car. He might start working on the second car immediately, but that would violate a condition that cars have to be passed to next workers as soon as they' re done (after seven minutes second worker would finish working on his part of second car, but the third worker would not be free to take over as he would still be working on the first car). That is the reason production of the second car is started after five minutes. Production of the third car starts after seven minutes. First car is finished after eight, second after nine and third after eleven seconds. Total time is then 11.
Được gửi lên bởi:  Alex & Friends 
Ngày:  20120105 
Thời gian chạy:  0.400s 
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ừ: ASM64 GOSU PERL6 PYPY RUST SED 
Nguồn bài:  COCI 20112012  Contest 3 
hide comments
20171101 16:53:54
THAM KHẢO THUẬT TOÁN VÀ CODE TẠI: http://yeulaptrinh.pw/1352/trakaspoj/ 

20171010 17:08:34
Trâu thôi nhé :)) Last edit: 20171011 17:05:50 

20120107 03:26:56 Alex & Friends
Sr mọi người, có chút nhầm lẫn trong test ví dụ, đã sửa! 

20120107 03:26:49 Alex & Friends
Last edit: 20120107 03:27:21 

20120106 16:02:08 King siêu kul
ps xem lại đề gốc đi. Cái giải thích đó là của ví dụ khác đấy. 

20120106 14:59:15 TLMN
Sao cái giải thích chả khớp gì với cái test vd vậy nhỉ @@ 