| Nộp bài | Các bài nộp | Làm tốt nhất | Về danh sách bài |
P131SUME - SUM1 E - Lựa chọn thí sinh |
Tại một ngân hà xa xôi, một kì thi lập trình sắp được tổ chức. Nhiệm vụ của bạn là chọn các thí sinh.
Có N học sinh, mỗi học sinh có kiến thức về mỗi dạng thi trong M dạng thi khác nhau. Kiến thức có thể được mô tả là một số thực. Bạn có thể gửi tối đa K học sinh tới kì thi, nhưng không học sinh nào có thể tham dự nhiều hơn một dạng thi. Đa số học sinh có thể tham dự ít nhất một dạng thi.
Mỗi học sinh, ta đã biết kiến thức của học sinh đó về mỗi dạng thi.
Chọn các thí sinh cho kì thi và các dạng thi chúng có thể tham dự trong kì thi, sao cho tổng các kiến thức là lớn nhất.
Input
Dòng đầu tiên của input chứa số các số nguyên N, M và K ( 1<=M<=100, 1<=K<=N<=100).
Mỗi dòng trong số M dòng tiếp theo mô tả kiễn thức về mỗi dạng thi.
Trong mỗi dòng, có N cặp (i, s), i là số thứ tự của học sinh, và s là số thực dương biểu thị cho kiến thức của học sinh đó về dạng thi tương ứng (0<=s<=10). Các cặp được sắp xếp theo kiến thức giảm dần. Các học sinh được đánh số từ 1 tới N.
Trong mỗi dòng, mỗi học sinh sẽ được xuất hiện một lần.
Output
In ra giá trị lớn nhất tổng các kiến thức của các học sinh đã được chọn, với độ chính xác một chữ số sau dấu thập phân.
Example
Test 1.
Input:
3 2 2
2 3.0 1 0.2 3 0.1
3 1.0 2 0.5 1 0.2
Output:
4.0
Giải thích: Phương án tối ưu nhất là lựa chọn học sinh thứ 2 ở lĩnh vực đầu tiên, và học sinh thứ 3 cho lĩnh vực thứ hai.
Tổng lượng kiến thức khi đó sẽ là 3.0 + 1.0 = 4.0 .
Test 2.
Input:
4 4 3
4 5.0 2 4.0 3 2.0 1 1.0
2 2.0 3 1.0 1 0.5 4 0.3
4 6.0 3 5.0 2 2.0 1 0.0
1 4.0 2 3.0 4 0.6 3 0.3
Output:
15.0
| Được gửi lên bởi: | adm |
| Ngày: | 2013-07-03 |
| Thời gian chạy: | 1s |
| Giới hạn mã nguồn: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Ngôn ngữ cho phép: | ASM32-GCC ASM32 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO JS-MONKEY KTLN OCT PAS-GPC PAS-FPC PERL PERL6 PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA |
