Đội ngũ hiệu quả nhất

Buổi 12 — Greedy Algorithm greedy sorting
Points
48
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
sortsearch
Submissions
Đề bài

Có $N$ kỹ sư, kỹ sư thứ $i$ có tốc độ làm việc $s_i$ và hệ số hiệu quả $e_i$. Bạn cần chọn ra tối đa $K$ kỹ sư (ít nhất $1$ người) để lập thành một đội. Hiệu suất của đội được tính bằng tổng tốc độ của các thành viên trong đội nhân với hệ số hiệu quả nhỏ nhất trong đội. Hãy tìm hiệu suất lớn nhất có thể, in kết quả theo phần dư khi chia cho $10^9 + 7$ (lưu ý: bạn cần tối đa hóa giá trị thực trước rồi mới lấy phần dư).

Dữ liệu vào
  • Dòng đầu tiên chứa hai số nguyên $N$ và $K$.
  • $N$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $s_i$ và $e_i$.
Dữ liệu ra

Một số nguyên duy nhất là hiệu suất lớn nhất tìm được chia lấy dư cho $10^9 + 7$.

Ví dụ
Input Output
6 2\n2 5\n10 4\n3 3\n1 9\n5 7\n2 2 60
6 3\n2 5\n10 4\n3 3\n1 9\n5 7\n2 2 68
Giới hạn
  • $1 \le K \le N \le 10^5$
  • $1 \le s_i \le 10^5$
  • $1 \le e_i \le 10^8$
Draft saved