#2015 · TỐI ƯU HÓA LỊCH THI OLYMPIC TIN HỌC 2025

Trường đại học công nghệ Tp.HCM (HUTECH) đăng cai tổ chức Olympic Tin học cấp quốc gia vào tháng 12/2025 với số lượng thí sinh dự thi đông kỷ lục.

Ban tổ chức phải sắp xếp lịch thi cho N thí sinh vào M phòng máy khác nhau sao cho không gây quá tải hệ thống, nhưng vẫn ưu tiên sử dụng các phòng có mạng ổn định.

Mỗi phòng máy i (1 \leq i \leq M) có:

• Sức chứa tối đa: C_i (số thí sinh tối đa có thể ngồi trong phòng)
• Độ ổn định mạng: S_i (số nguyên, càng lớn càng ổn định)

Với K đường dây mạng 2 chiều, mỗi đường sẽ nối 2 phòng máy u và v. Các phòng nối với nhau trực tiếp hoặc qua trung gian sẽ đều thuộc cùng một cụm phòng kết nối.

Nếu một phòng quá đông các phòng cùng cụm kết nối sẽ bị chậm, vì vậy tổng số thí sinh trong mỗi cụm phòng kết nối không được vượt quá một mức L đã cho.

Yêu cầu: Hãy sắp xếp N thí sinh vào M phòng, sao cho:

• Mỗi phòng không vượt quá sức chứa.
• Mỗi cụm phòng kết nối không vượt quá tổng L thí sinh.

• Tổng độ ổn định mạng tổng thể phải lớn nhất có thể, tính bằng: F = \sum_{i=1}^{M} S[i] \times X[i]

  Trong đó: • X[i] = số thí sinh được phân vào phòng i. Nếu phòng không chứa ai → X[i] = 0 → phòng không đóng góp điểm.

Nếu có nhiều cách sắp xếp thỏa mãn, hãy chọn cách có tổng độ ổn định mạng F là lớn nhất. Nếu không thể sắp xếp → Output 0.

• Dòng 1: 4 số nguyên dương N M K L cách nhau bằng kí tự khoảng trắng
• Dòng 2: M số nguyên dương từ C_1C_2 … C_m cách nhau bằng kí tự khoảng trắng là sức chứa tối đa của M phòng từ phòng 1 đến M.
• Dòng 3: M số nguyên dương từ S_1S_2 … S_m cách nhau bằng kí tự khoảng trắng là độ ổn định mạng của phòng thứ 1 đến M.
• K dòng tiếp theo, mỗi dòng có 2 số nguyên dương u và v cách nhau bằng kí tự khoảng trắng là đường dây mạng nối phòng u với phòng v.

• Một số nguyên: → độ ổn định mạng lớn nhất có thể đạt được
• Hoặc 0 nếu không thể xếp lịch.

• 1 \leq N \leq 100000
• 1 \leq M \leq 100000
• 0 \leq K \leq 100000
• 0 \leq L \leq 100000
• 1 \leq C_i \leq 10^9
• 0 \leq S_i \leq 10^9