JOI 2026 - Scarecrows 2

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Dạng bài
Ngôn ngữ cho phép
Assembly, Awk, C, C#, C++, Clang, Cobol, D, Groovy, Haskell, JS, Java, Kotlin, Lua, Node JS, OCaml, ObjectiveC, Output, PHP, Pascal, Perl, Prolog, Pypy, Pypy 3, Python, Ruby, Rust, Scala, Scratch, Swift
Điểm: 2500 (p) Thời gian: 2.5s Bộ nhớ: 1G Input: bàn phím Output: màn hình

Cánh đồng rộng lớn của làng JOI được biểu diễn bằng mặt phẳng \(xy\) vô hạn, trong đó chiều dương của trục \(x\) là hướng Đông, chiều dương của trục \(y\) là hướng Bắc. Thị trưởng muốn đặt các con bù nhìn để bảo vệ cánh đồng khỏi kẻ địch. Mỗi bù nhìn bảo vệ một vùng tùy theo vị trí và hướng quay của nó. Có \(N\) kế hoạch đặt bù nhìn, được đánh số từ \(1\) đến \(N\). Thực hiện kế hoạch thứ \(i\) tốn chi phí \(C_i\) và đặt một bù nhìn theo ba số nguyên \(T_i, X_i, Y_i\) như sau:

  • Nếu \(T_i = 1\), bù nhìn ở \((X_i, Y_i)\) quay về Tây và bảo vệ mọi điểm có \(x \le X_i\).
  • Nếu \(T_i = 2\), bù nhìn ở \((X_i, Y_i)\) quay về Đông và bảo vệ mọi điểm có \(x \ge X_i\).
  • Nếu \(T_i = 3\), bù nhìn ở \((X_i, Y_i)\) quay về Nam và bảo vệ mọi điểm có \(y \le Y_i\).
  • Nếu \(T_i = 4\), bù nhìn ở \((X_i, Y_i)\) quay về Bắc và bảo vệ mọi điểm có \(y \ge Y_i\).

Hãy chọn một số kế hoạch sao cho mọi điểm trên mặt phẳng được bảo vệ bởi ít nhất \(K\) bù nhìn, và tổng chi phí là nhỏ nhất. Nếu không thể, in ra -1.

Dữ liệu vào

  • Dòng đầu chứa hai số nguyên \(N\), \(K\).
  • \(N\) dòng tiếp theo, dòng thứ \(i\) chứa bốn số nguyên \(T_i\), \(X_i\), \(Y_i\), \(C_i\).

Dữ liệu ra

In ra chi phí nhỏ nhất cần thiết, hoặc -1 nếu không thể bảo vệ mọi điểm bởi ít nhất \(K\) bù nhìn.

Ràng buộc

  • \(1 \le K \le N \le 200000\).
  • \(T_i \in \{1,2,3,4\}\).
  • \(0 \le X_i, Y_i \le 10^9\).
  • Các cặp tọa độ \((X_i, Y_i)\) đôi một khác nhau.
  • \(0 \le C_i \le 10^9\).
  • Mọi giá trị đầu vào đều là số nguyên.

Phân nhóm

  • Nhóm 1 (4 điểm): \(K = 1\).
  • Nhóm 2 (6 điểm): \(K \le 2\).
  • Nhóm 3 (11 điểm): \(N \le 500\), \(K \le 300\).
  • Nhóm 4 (27 điểm): \(N \le 6000\).
  • Nhóm 5 (19 điểm): \(N \le 75000\).
  • Nhóm 6 (33 điểm): Không có ràng buộc bổ sung.

Ví dụ

Ví dụ 1

Input 
7 1
2 45 21 96
1 5 85 70
1 36 73 78
1 28 12 80
2 15 49 21
1 45 11 96
2 63 26 19
Output 
99
Giải thích

Chẳng hạn, thực hiện kế hoạch \(3\) và \(5\):

  • Kế hoạch \(3\) đặt bù nhìn tại \((36,73)\) quay về Tây, tốn \(78\).
  • Kế hoạch \(5\) đặt bù nhìn tại \((15,49)\) quay về Đông, tốn \(21\).

Khi đó mọi điểm trên mặt phẳng được ít nhất một bù nhìn bảo vệ. Ví dụ, điểm \((0,0)\) được bù nhìn tại \((36,73)\) quay về Tây của kế hoạch \(3\) bảo vệ. Tổng chi phí là \(78+21=99\). Không thể bảo vệ mọi điểm bởi ít nhất một bù nhìn với chi phí nhỏ hơn, nên kết quả là \(99\).

Ví dụ này thỏa mãn ràng buộc của tất cả các nhóm.

Ví dụ 2

Input 
7 3
2 45 21 96
1 5 85 70
1 36 73 78
1 28 12 80
2 15 49 21
1 45 11 96
2 63 26 19
Output 
-1
Giải thích

Ví dụ này chỉ khác ví dụ \(1\) ở giá trị \(K\). Không thể bảo vệ mọi điểm trên mặt phẳng bởi ít nhất \(3\) bù nhìn, nên kết quả là \(-1\).

Ví dụ này thỏa mãn các ràng buộc của nhóm \(3,4,5,6\).

Ví dụ 3

Input 
19 5
2 36 42 64
2 7 89 74
1 0 15 82
1 10 63 55
2 58 28 19
2 45 91 3
2 2 34 97
1 7 55 82
1 17 12 17
2 59 76 82
1 7 4 68
2 51 98 47
1 51 21 38
2 19 0 72
1 73 73 11
2 62 19 74
1 45 7 94
1 79 32 21
1 85 50 21
Output 
315
Giải thích

Ví dụ này thỏa mãn các ràng buộc của nhóm \(3,4,5,6\).

Ví dụ 4

Input 
8 3
4 4 21 80
2 59 65 69
4 63 36 3
2 29 13 23
1 37 45 95
2 79 14 89
3 91 54 76
1 85 46 62
Output 
328
Giải thích

Ví dụ này thỏa mãn các ràng buộc của nhóm \(3,4,5,6\).

Nguồn

JOI 2025/2026 Final Stage, Competition 3, problem Scarecrows 2. Tài liệu gốc của Japanese Committee for IOI được phát hành theo giấy phép CC BY-SA 4.0.

Tệp

Bình luận

Mới nhất
Tải bình luận...

Không có bình luận nào.

Kỳ thi: