Khảo sát lưu lượng xe


Submit solution

Points: 3.2 (partial)
Time limit: 1.0s
Memory limit: 67M

Author:
Problem types
Allowed languages
Ada, Assembly, Awk, C, C++, C11, CLANG, CLANGX, Classical, COBOL, Coffee, CSC, D lang, DART, F95, FORTH, Fortrn, GAS32, GO, Haskell, Itercal, Java, kotlin, LEAN, LISP, LUA, MONOVB, Nasm, OCAML, Pascal, Perl, php, PIKE, prolog, Pypy, Python, Ruby 2, RUST, Scala, SCM, SED, SWIFT, TCL, TUR, V8JS, VB, ZIG

Trên một con đường có m trạm xăng (trạm 1, 2, ..., m), n xe ô tô đều xuất phát từ trạm 1. Bạn hãy lập trình tính xem có bao nhiêu xe dừng ở mỗi trạm xăng, biết rằng:

  • Mỗi cây xăng đều chỉ cung cấp một lượng xăng tối đa nào đó.
  • Đi hết 1 đơn vị độ dài tốn đúng 1 đơn vị lượng xăng.
  • Các xe trước khi xuất phát từ trạm nào đều nạp một lượng xăng tối đa ở trạm đó.
  • Các xe chỉ rời trạm khi đã đủ xăng đi tới trạm tiếp theo.

Chú ý: Nếu các xe đều có thể đi qua trạm cuối, ta vẫn tính là dừng ở trạm cuối.

Đầu vào

Dòng đầu tiên gồm hai số tự nhiên m,n (2m,n105), số trạm và số xe ô tô (xuất phát từ trạm 1) cần khảo sát.

Dòng thứ hai chứa m số tự nhiên không quá 109, số thứ i (1im) là số xăng tối đa trạm thứ i có thể cung cấp cho một xe.

Dòng thứ ba chứa m1 số tự nhiên không quá 109, số thứ i (1im1) là khoảng cách từ trạm thứ i tới trạm thứ i+1.

Dòng cuối cùng chứa n số tự nhiên không quá 109 là lượng xăng của các xe ô tô.

Đầu ra

Một dòng duy nhất chứa m số tự nhiên, số thứ i là số lượng xe dừng ở trạm i.

Subtask

30% số test có mn106.

Ví dụ

Đầu vào:

Copy
5 5
1 0 1 0 1
1 1 1 1
0 1 2 3 4

Đầu ra:

Copy
0 1 0 1 3

Giải thích: Xe thứ nhất dừng ở trạm 2, xe thứ hai dừng ở trạm 4, ba xe còn lại đều có thể đi qua trạm cuối.

QDUY

Comments

There are no comments at the moment.