How Did We Get Here?
How Did We Get Here? - Have every effect applied at the same time
EmeraldBoyGamer đang setup mọi thứ để đạt được tiến trình "How Did We Get Here", cậu cần đạt được tất cả hiệu ứng trong cùng một lúc. Sau khi cài một loại mod nào đó, trong game hiện có \(k\) loại hiệu ứng, đánh số từ 1 đến \(k\). Với loại hiệu ứng \(i\), cậu đặt một button ở vị trí \((x_i, y_i)\) dẫn tới một hệ thống máy móc dùng để kích hoạt hiệu ứng đó. Do một vài giới hạn, hiệu ứng chỉ kéo dài tối đa \(d_i\) giây.
Cậu dự định xuất phát tại \((s_x, s_y)\) vào giây 0 và di chuyển với tốc độ 1 ô/giây, vì vậy, khi đi từ \((a, b)\) tới \((c, d)\), cậu mất \(|a - c| + |b - d|\) giây. Cậu được đứng chờ, và có thể đi qua một button mà không kích hoạt nó.
Khi đứng tại button của hiệu ứng \(i\), cậu có thể kích hoạt nó (xem như không mất thời gian). Nếu kích hoạt vào giây \(t\) thì cậu có hiệu ứng \(i\) trong khoảng thời gian \([t, t + d_i)\). Kích hoạt lại thì thời hạn được tính lại từ đầu. Tuy nhiên, một vài hiệu ứng sau khi có thì lại xóa đi một vài hiệu ứng khác (ví dụ như khi có được Hero of the Village thì sẽ mất Bad Omen). Và sau khi cài mod thì mọi thứ lại càng phức tạp hơn, sau khi nhận được hiệu ứng \(i\), các hiệu ứng \(x_{i,j}\) đều bị xóa.
Hãy cho biết thời gian ngắn nhất để cậu có thể đạt được tiến trình này, hoặc cho biết nếu cậu cần phải build một hệ thống mới nếu không thể.
Dữ liệu
- Dòng đầu tiên chứa các số nguyên \(k, s_x, s_y \ (1\le k \le 17, 1 \le s_x, s_y \le 10^5)\);
- \(k\) cặp dòng tiếp theo, mỗi cặp có cấu trúc sau:
- Dòng đầu tiên chứa các số nguyên \(x_i, y_i, d_i \ (1 < x_i, y_i \le 10^5)\);
- Dòng tiếp theo bắt đầu bằng một số nguyên \(c_i\), tiếp theo sau đó là \(c_i\) số nguyên \(x_{i,j} \ (0\le c_i \le k; 1\le x_{i,j} \le k)\).
Kết quả
- Kết quả bài toán, hoặc in ra -1 nếu cậu không thể đạt được tiến trình.
Chấm điểm
- Subtask 1 (30%): \(k \le 8\).
- Subtask 2 (20%): \(c_i = 0\).
- Subtask 3 (20%): \(d_i = 10^9\).
- Subtask 4 (30%): Không có giới hạn gì thêm.
Ví dụ
Ví dụ 1
input
3 1 1
2 1 20
0
7 1 100
0
7 3 3
0
output
8
Ví dụ 2
input
3 1 1
2 1 20
0
7 1 100
1 1
7 3 3
0
output
18
Giải thích
- Ở ví dụ 1, đi theo thứ tự 1, 2, 3. Kích hoạt ở các giây 1, 6, 8. Tại giây 8, hiệu ứng 1 còn tới giây 21, hiệu ứng 2 còn tới giây 106, hiệu ứng 3 vừa nhận. Đáp án là 8.
- Ở ví dụ 2, nguồn 2 xóa hiệu ứng 1, nên 2 phải đứng trước 1:
- Thứ tự 2, 3, 1 chỉ mất 15 giây, nhưng hiệu ứng 3 (kéo dài 3 giây) hết hạn trước khi tới nguồn 1.
- Thứ tự 3, 2, 1 cũng không khả thi vì lý do tương tự.
- Thứ tự 2, 1, 3, kích hoạt ở các giây 6, 11, 18 là thứ tự khả thi, kéo dài 18 giây.
Comments