Lịch vắt sữa

Điểm: 1,00 (OI)

Giới hạn thời gian: 1.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Có $N$ con bò cần được vắt sữa, bò $i$ mất $T_{i}$ đơn vị thời gian. Các bò có thể được vắt sữa song song (đồng thời), nhưng có $M$ ràng buộc thứ tự: bò $A$ phải được vắt sữa xong trước khi bò $B$ bắt đầu.

Tìm thời gian tối thiểu để vắt sữa tất cả các bò.

Dữ liệu vào

Dòng 1: Hai số nguyên $N$ và $M$
Dòng $i + 1$ (với $1 \leq i \leq N$ ): Số nguyên $T_{i}$ — thời gian vắt sữa bò $i$
Dòng $N + i + 1$ (với $1 \leq i \leq M$ ): Hai số nguyên $A$ và $B$ — bò $A$ phải xong trước bò $B$

Dữ liệu ra

Một số nguyên duy nhất: thời gian tối thiểu

Ràng buộc

$1 \leq N \leq 10000$
$0 \leq M \leq 50000$
$1 \leq T_{i} \leq 100000$
Không có phụ thuộc vòng tròn

Ví dụ

Input	Output	Giải thích
3 1 10 5 6 3 2	11	Bò 3 phải xong trước bò 2. Bò 1 (T=10) và bò 3 (T=6) vắt song song → xong lúc t=10 và t=6. Bò 2 bắt đầu lúc t=6, xong lúc t=11.

Bình luận

Không có bình luận tại thời điểm này.