Nông Trại Của FJ

Điểm: 1,00 (OI)

Giới hạn thời gian: 1.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ông dân John trồng $N$ cây với chiều cao ban đầu $h_{1}, h_{2}, \dots, h_{N}$ và tốc độ tăng trưởng hàng ngày $a_{1}, a_{2}, \dots, a_{N}$ . Sau $d$ ngày, chiều cao của cây thứ $i$ là $h_{i} + d \cdot a_{i}$ .

Nông dân John muốn mỗi cây $i$ có đúng $t_{i}$ cây khác cao hơn nó (tức là cây $i$ đứng ở vị trí $t_{i} + 1$ khi sắp xếp chiều cao giảm dần, các $t_{i}$ phân biệt đôi một). Hãy tìm số ngày tối thiểu cần thiết để đạt được cấu hình này, hoặc xác định nếu không thể.

Lưu ý: Tại thời điểm đó, không có hai cây nào có cùng chi��u cao.

Dữ liệu vào

Dòng $1$ : Số nguyên $T$ ( $1 \leq T \leq 10$ ) — số bộ test.
Với mỗi bộ test:
- Dòng $1$ : Số nguyên $N$ ( $1 \leq N \leq 2 \cdot 10^{5}$ ).
- Dòng $2$ : $N$ số nguyên $h_{1}, \dots, h_{N}$ ( $1 \leq h_{i} \leq 10^{9}$ ).
- Dòng $3$ : $N$ số nguyên $a_{1}, \dots, a_{N}$ ( $1 \leq a_{i} \leq 10^{9}$ ).
- Dòng $4$ : $N$ số nguyên phân biệt $t_{1}, \dots, t_{N}$ ( $0 \leq t_{i} \leq N - 1$ ).

Dữ liệu ra

In ra $T$ dòng, mỗi dòng là số ngày tối thiểu cần thiết, hoặc $- 1$ nếu không thể.

Ràng buộc

Tổng $N$ qua tất cả các bộ test $\leq 2 \cdot 10^{5}$ .
Cần sử dụng kiểu dữ liệu 64-bit.
Test $3$ : $N \leq 2$ .
Các test $4$ - $5$ : $N \leq 50$ .
Các test $6$ - $8$ : $N \leq 10^{3}$ .
Các test $9$ - $13$ : Không có ràng buộc thêm.

Ví dụ

Input	Output	Giải thích
6 1 10 1 0 2 7 3 8 10 1 0 2 3 6 10 8 0 1 2 7 3 8 9 1 0 2 7 7 8 8 0 1 2 7 3 8 8 1 0	0 3 2 5 -1 -1	6 bộ test. Bộ 1 ( $N = 1$ ): chỉ 1 cây, $t = 0$ luôn thỏa. Bộ 5 ( $h = [7, 7], a = [8, 8], t = [0, 1]$ ): hai cây cùng chiều cao và tốc độ nên không bao giờ phân biệt được, kết quả $- 1$ .

Bình luận

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