Clash!

Đ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

Bác John chơi một trò chơi thẻ bài. Có $N$ lá bài, mỗi lá có chi phí $a_{i}$ (tính bằng moolixir). Bác giữ trên tay $H$ lá bài.

Khởi tạo:

Tay bài chứa các lá $1$ đến $H$
Hàng chờ rút bài chứa các lá $H + 1$ đến $N$ theo thứ tự

Cơ chế chơi:

Trò chơi bắt đầu tại thời điểm $0$ với $0$ moolixir
Trước mỗi giây nguyên $t = 1, 2, 3, \dots$ , moolixir tăng thêm $1$
Một lá bài chỉ được chơi khi chi phí không vượt quá moolixir hiện tại (chi phí bị trừ đi)
Khi chơi một lá, rút lá đầu hàng chờ vào tay, lá vừa chơi đặt cuối hàng chờ

Điều kiện thắng: Có $k$ lá bài được đánh dấu là "điều kiện thắng". Nếu tay bài có ít nhất một điều kiện thắng, lá tiếp theo bắt buộc phải là điều kiện thắng.

Bác John chơi tối ưu. Cho $Q$ truy vấn, mỗi truy vấn là thời điểm $t$ — tìm số điều kiện thắng tối đa có thể chơi trong thời gian $t$ .

Dữ liệu vào

Dòng 1: Hai số nguyên $N$ và $H$ ( $2 \leq N \leq 2 \times 10^{5}$ , $1 \leq H < N$ )
Dòng 2: $N$ số nguyên $a_{1}, \dots, a_{N}$ ( $1 \leq a_{i} \leq 10^{9}$ )
Dòng 3: Số nguyên $k$ ( $1 \leq k \leq N$ )
Dòng 4: $k$ chỉ số của các lá điều kiện thắng
Dòng 5: Số nguyên $Q$ ( $1 \leq Q \leq 2 \times 10^{5}$ )
Dòng 6: $Q$ số nguyên $t$ ( $1 \leq t \leq 10^{18}$ )

Dữ liệu ra

Với mỗi truy vấn, in ra số điều kiện thắng tối đa có thể chơi.

Ràng buộc

$2 \leq N \leq 2 \times 10^{5}$
$1 \leq a_{i} \leq 10^{9}$
$1 \leq Q \leq 2 \times 10^{5}$
$1 \leq t \leq 10^{18}$

Ví dụ

Input	Output	Giải thích
6 3 2 4 3 5 7 6 2 1 4 6 1 2 3 7 10 1000000000000000	0 1 1 2 2 142857142857143	Tại $t = 2$ : đủ moolixir chơi lá 1 (chi phí 2, là điều kiện thắng).

Ghi chú

Test 2-3: $N, Q \leq 100$
Test 4-5: $H = 1$
Test 6-11: Không ràng buộc bổ sung

Bình luận

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