Declining Invitations

Điểm: 1,00 (OI)

Giới hạn thời gian: 2.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

$N$ thí sinh với thứ hạng phân biệt từ $1$ đến $N$ tham gia một cuộc thi. Có $C$ tiêu chí, mỗi thí sinh thỏa mãn một số tiêu chí nhất định.

Quá trình mời diễn ra tuần tự qua các tiêu chí: với tiêu chí $i$ , mời $f_{i}$ thí sinh có thứ hạng cao nhất (thứ hạng nhỏ nhất) thỏa mãn tiêu chí đó mà chưa được mời. Nếu còn ít hơn $f_{i}$ thí sinh như vậy, mời tất cả.

Cho một hoán vị $p$ biểu thị thứ tự từ chối. Với mỗi $i$ từ $0$ đến $N - 1$ , hãy tính tổng thứ hạng của các thí sinh được mời khi $i$ thí sinh đầu tiên trong $p$ đã từ chối (thí sinh từ chối sẽ không được mời).

Dữ liệu vào

Dòng 1: Hai số nguyên $N$ và $C$ ( $1 \leq N, C \leq 10^{5}$ ).
Dòng 2: $C$ số nguyên $f_{1}, f_{2}, \dots, f_{C}$ .
Dòng 3: $N$ số nguyên $p_{1}, p_{2}, \dots, p_{N}$ .
$N$ dòng tiếp theo: Dòng thứ $i$ bắt đầu bằng $n_{i}$ , sau đó là $n_{i}$ số nguyên phân biệt trong $[1, C]$ - các tiêu chí mà thí sinh thứ hạng $i$ thỏa mãn.

Dữ liệu ra

In $N$ dòng, dòng thứ $i$ là tổng thứ hạng của các thí sinh được mời khi $i - 1$ thí sinh đầu tiên trong $p$ đã từ chối.

Ràng buộc

$1 \leq N, C \leq 10^{5}$
$\sum n_{i} \leq 10^{6}$
Input 4-6: $N, C \leq 10^{3}$ , $\sum n_{i} \leq 10^{4}$
Input 7-8: $C = 1$
Input 9-10: $C = 2$

Ví dụ

Input	Output	Giải thích
5 1 3 5 1 3 2 4 1 1 1 1 1 1 1 1 1 1	6 6 9 6 4	Ban đầu mời 3 thí sinh hạng nhỏ nhất: {1,2,3}, tổng=6. Sau khi 5 từ chối (không ảnh hưởng): vẫn 6. Sau khi 1 từ chối: mời {2,3,4}, tổng=9.
5 4 1 1 1 1 1 2 3 4 5 1 1 2 1 2 2 2 3 2 3 4 1 4	10 14 12 9 5	4 tiêu chí mỗi cái mời 1 người.

Bình luận

Không có bình luận tại thời điểm này.