Đếm tần suất nhiều từ khóa (Aho-Corasick)
Points
80
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Đề bài
Có $n$ người xếp hàng tại một quầy phục vụ. Người thứ $i$ cần thời gian phục vụ là $t_i$. Một người sẽ không bị thất vọng nếu tổng thời gian chờ đợi của họ (tức tổng thời gian phục vụ của tất cả những người đứng trước họ) không vượt quá $t_i$. Bạn được phép sắp xếp lại thứ tự xếp hàng tùy ý. Hỏi tối đa có bao nhiêu người không bị thất vọng?
Dữ liệu vào
- Dòng đầu chứa số nguyên $n$ ($1 \le n \le 10^5$).
- Dòng thứ hai chứa $n$ số nguyên $t_1, t_2, \dots, t_n$ ($1 \le t_i \le 10^9$).
Dữ liệu ra
3
aba
ba
c
3
3
0
Giới hạn
$1 \le |T| \le 5 \cdot 10^5$, $1 \le K \le 10^5$, tổng độ dài các từ khóa $\sum |P_i| \le 5 \cdot 10^5$.
Community Discussion