Editorial for Thiếu hụt
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Submitting an official solution before solving the problem yourself is a bannable offence.
Để làm được bài này, ta cần một chiến thuật trả tiền làm cho công ty này càng 'thâm hụt' càng tốt.
Bạn cần lưu 2 mảng \(pay[i]\) và \(receive[i]\), lần lượt là số tiền công ty phải trả / được nhận vào ngày thứ \(i\).
Với mỗi yêu cầu chuyển khoản vào công ty, ta sẽ chuyển khoản cho công ty vào ngày trễ nhất : \(receive[d2] = receive[d2] + t\)
Với mỗi yêu cầu trả tiền, ta chỉ có một cách : \(pay[d1] = pay[d1] + |t|\)
Sau đó, ta chỉ đơn giản duyệt qua từng ngày trong \(m\) ngày, luôn ưu tiên trả tiền trước khi nhận. Tại một thời điểm bất kì, nếu ngân sách giảm xuống dưới \(0\), ta in ra YES.
Comments