Cắt Cỏ Nghịch Ngợm

Điểm: 1,00 (OI)

Giới hạn thời gian: 4.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

Có $N$ bông hoa trên lưới $[0, T] \times [0, T]$ , hoa thứ $i$ ở tọa độ $(x_{i}, y_{i})$ . Không có hai bông hoa nào có cùng tọa độ $x$ hoặc $y$ .

Bessie muốn chọn tập con lớn nhất các bông hoa nằm trên một đường đi từ $(0, 0)$ đến $(T, T)$ chỉ di chuyển sang phải hoặc lên trên. Các hoa được chọn phải có cả tọa độ $x$ và $y$ tăng dần.

Trong tất cả tập con lớn nhất, hãy tìm tập con sao cho diện tích cỏ bị cắt là nhỏ nhất. Diện tích này bằng tổng diện tích hình chữ nhật giữa các điểm liên tiếp (bao gồm $(0, 0)$ ở đầu và $(T, T)$ ở cuối):

$\sum_{i = 0}^{| S |} (x_{i + 1} - x_{i}) (y_{i + 1} - y_{i})$

với $(x_{0}, y_{0}) = (0, 0)$ và $(x_{| S | + 1}, y_{| S | + 1}) = (T, T)$ .

Dữ liệu vào

Dòng đầu: hai số nguyên $N$ và $T$ ( $1 \leq N \leq 3 \times 10^{5}$ , $1 \leq T \leq 10^{6}$ )
$N$ dòng tiếp theo: $x_{i} y_{i}$ ( $1 \leq x_{i}, y_{i} \leq T - 1$ )

Dữ liệu ra

Một số nguyên: diện tích cỏ bị cắt nhỏ nhất.

Ràng buộc

$1 \leq N \leq 3 \times 10^{5}$ , $1 \leq T \leq 10^{6}$
Không có hai hoa nào có cùng tọa độ $x$ hoặc $y$

Ví dụ

Input	Output	Giải thích
5 20 19 1 2 6 9 15 10 3 13 11	117	Tập con tối ưu: ${(10, 3), (13, 11)}$ . Diện tích: $10 \times 3 + 3 \times 8 + 7 \times 9 = 30 + 24 + 63 = 117$ .
2 10 3 4 7 8	34	Chọn cả hai hoa $(3, 4)$ và $(7, 8)$ . Diện tích: $3 \times 4 + 4 \times 4 + 3 \times 2 = 12 + 16 + 6 = 34$ .

Bình luận

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