Đếm tần suất nhiều từ khóa (Aho-Corasick)

Buổi 55 — Trie & Aho-Corasick Buổi 69-70 — Mock Tổng hợp Strings
Points
80
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Submissions
Đề 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$.

Draft saved