SUBD - Nợ báo cáo
Giới hạn- Thời gian: 1.0s
- Bộ nhớ: 1536MB
- Mã nguồn: 50000 bytes
Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.
Trở lại với năm 2013. Sau nhiều tuần rong ruổi trên khắp nước Mỹ, Trung trở về Atlanta tiếp tục học tại đại học X. Về đến nhà Trung mới biết trong đợt nghỉ đông vừa rồi, mỗi lớp học của Trung đều yêu cầu sinh viên viết báo cáo (lab report). Do mải mê đi chơi nên Trung chưa viết bài nào cả. Trung học N lớp, lớp thứ i yêu cầu M i report. Nếu không nộp đủ số report của một môn trước deadline thì Trung sẽ phải học lại môn đó. Do không muốn học lại môn nào cả nên Trung chọn cách khác : đóng tiền phạt. Nếu Trung nộp một report trễ T giây và bài này có hệ số là A thì Trung sẽ đóng khoản tiền phạt là T x A cent.
Để cho việc viết dễ dàng hơn, Trung quyết định sẽ lần lượt viết tất cả các report của cùng một môn. Sau khi đã xong hết một môn Trung mới chuyển sang môn khác. Nếu môn i có M i report, Trung có thể viết M i report này theo bất kì thứ tự nào. Trung cũng có thể chọn thứ tự môn bất kì để viết report. Hiển nhiên Trung sẽ chọn thứ tự môn và report sao cho tổng số tiền đóng phạt là nhỏ nhất. Nếu có nhiều cách sắp xếp, Trung sẽ chọn cách để thứ tự từ điển của dãy các môn học theo trình tự viết nhỏ nhất. Nếu trong một môn có nhiều cách sắp xếp các report, Trung cũng sẽ chọn cách để dãy thứ tự các report trong môn đó theo trình tự viết nhỏ nhất.
Coi như tất cả các report có cùng deadline và ngay sau deadline Trung sẽ bắt tay vào viết report.
Input
Dòng đầu tiên gồm số nguyên dương N – số môn học.
N nhóm dòng tiếp theo, nhóm dòng thứ i có cấu trúc như sau :
- dòng đầu là M i – số report của môn i
- dòng thứ 2 gồm M i số nguyên dương T i,j là thời gian (tính theo giây) Trung cần để viết bài report thứ j của môn i
- dòng thứ 3 gồm M i số nguyên dương A i,j là hệ số bài report thứ j của môn i
Giới hạn : 1 <= N <= 10 5 , 1 <= M i <= 2 x 10 5
1 <= A i,j , T i,j <= 5 x 10 5
Tổng số report không quá 3 x 10 5 .
Trong 30% số test, N = 1.
Output
Dòng đầu tiên ghi số nguyên S – tổng tiền phạt Trung phải đóng.
N nhóm dòng tiếp theo, nhóm thứ i gồm 2 dòng có cấu trúc :
- dòng đầu là K– số thứ tự của môn học thứ i mà Trung viết report
- dòng thứ 2 gồm dãy số nguyên dương B K (gồm M K số) là số thứ tự các report của môn K theo trình tự được viết.
Example
Input: 2 2 1 1 1 2 2 2 2 3 4 Output: 36 2 2 1 1 2 1
Gỉải thích : đầu tiên viết report của môn 2, nộp phạt 4x2 + 3x(2+2) = 20cent. Sau đó chuyển qua viết report của môn 1, nộp phạt tiếp 2 * (1+2+2) + 1 * (1+1+2+2) = 16 cent. Tổng tiền nộp phạt 20+16=36 cent
- Người up: yellowflash12
- Nguồn bài: by winterwolf94