Marathon (Silver)

Điểm: 1,00 (OI)

Giới hạn thời gian: 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$ điểm kiểm tra theo thứ tự, với tọa độ cho trước. Cần đi qua tất cả các điểm theo thứ tự từ điểm $1$ đến điểm $N$ , nhưng được phép bỏ qua tối đa $K$ điểm kiểm tra trung gian (không được bỏ điểm $1$ và điểm $N$ ). Khoảng cách giữa hai điểm là khoảng cách Manhattan: $| x_{1} - x_{2} | + | y_{1} - y_{2} |$ .

Tìm tổng quãng đường tối thiểu cần đi.

Dữ liệu vào

Dòng đầu chứa hai số nguyên $N$ và $K$ .

$N$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $x_{i}$ và $y_{i}$ — tọa độ điểm kiểm tra thứ $i$ .

Dữ liệu ra

Một số nguyên duy nhất — quãng đường tối thiểu.

Ràng buộc

$3 \leq N \leq 500$
$0 \leq K < N$ , $K \leq N - 2$
$- 1000 \leq x_{i}, y_{i} \leq 1000$

Ví dụ

Input	Output	Giải thích
5 2 0 0 8 3 1 1 10 -5 2 2	4	Bỏ điểm (8,3) và (10,-5). Đi 1→3→5: (0,0)→(1,1)→(2,2), khoảng cách = 2 + 2 = 4.
10 0 -25 60 91 -64 47 56 20 19 -69 -11 -69 -80 -89 -8 74 -33 20 -72 42 30	1153	K=0, không được bỏ điểm nào, đi tất cả 10 điểm theo thứ tự.

Bình luận

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