USACO 2022 - Tháng 12 - Hạng Vàng - Bộ đề bài

#	Bài tập	Điểm	Thời gian:	Giới hạn bộ nhớ
1	USACO 2022 December Contest, Gold, Bribing Friends	100 (p)	2.0s	256M
2	USACO 2022 December Contest, Gold, Mountains	100 (p)	5.0s	512M
3	USACO 2022 December Contest, Gold, Strongest Friendship Group	100 (p)	2.0s	256M

1. USACO 2022 December Contest, Gold, Bribing Friends

Điểm: 100 (p) Thời gian: 2.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Bessie muốn xem bộ phim Bovine Genomics: The Documentary nhưng mà hổng có mún đi một mình. Hổng may, mấy bẹn thân cũng hổng có hứng đi với Bessie! Vì vậy, Bessie cần phải hối lộ xíu để những người bạn này đi xem phim cùng. Ả có $2$ cách để hối lộ: đồng tiền mooney hoặc kem ốc quế.

Bessie có $N$ $(1 \le N \le 2000)$ người bạn. Tuy nhiên, không phải người bạn nào cũng như nhau! Người bạn $i$ có độ nổi tiếng là $P_i$ $(1 \le P_i \le 2000)$, và Bessie muốn cực đại hoá tổng độ nổi tiếng của những người bạn đi cùng ả ta đến rạp phim. Người bạn $i$ sẵn sàng đi cùng với Bessie nếu như ả đưa cho $C_i$ $(1 \le C_i \le 2000)$ đồng mooney và người bạn này sẽ giảm giá cho Bessie đi $1$ đồng mooney nếu ả đưa cho $X_i$ $(1 \le X_i \le 2000)$ cây kem ốc quế. Bessie có thể được giảm giá bao nhiêu tuỳ thích miễn là số đồng mooney được giảm không vượt quá số tiền mà Bessie cần đưa cho người bạn này.

Bessie có $A$ đồng mooney và $B$ cây kem trong ví $(0 \le A, B \le 2000)$. Hãy giúp cô ấy tìm ra tổng độ nổi tiếng lớn nhất có thể nếu cô ấy sử dụng mooney và kem một cách tối ưu.

Input

Dòng $1$ chưa ba số nguyên $N, A, B$.
Trong $N$ dòng tiếp theo, mỗi dòng thứ $i$ là ba số nguyên $P_i, C_i, X_i$.

Output

Tổng độ nổi tiếng lớn nhất.

Scoring

Subtask $1$: $N \le 5, C_i = 1$.
Subtask $2$: $B = 0$.
Subtask $3$: $N, A, B, P_i, C_i, X_i \le 50$.
Subtask $4$: $$N, A, B, P_i, C_i, X_i \le 200$.
Subtask $5$: Không có thêm ràng buộc.

Test 1

Input

Output

Note

Bessie có thể cho người bạn $1$ $4$ moonies và $4$ cây kem, $6$ moonies và $3$ cây kem cho người bạn $3$ để có tổng độ nổi tiếng lớn nhất là $5 + 10 = 15$.

2. USACO 2022 December Contest, Gold, Mountains

Điểm: 100 (p) Thời gian: 5.0s Bộ nhớ: 512M Input: bàn phím Output: màn hình

Lưu ý: Giới hạn thời gian là 5s. Giới hạn bộ nhớ là 512MB

Có $N$ ngọn núi $(1 \le N \le 2000)$ được đặt cách nhau trên cùng một dãy núi của nông dân John. Các ngọn núi này được thể hiện bởi một dãy độ cao $h_1, h_2, \dots, h_n$. Đứng ở ngoại núi thứ $i$, bạn có thể nhìn thấy ngọn núi thứ $j$ nếu như không có ngọn núi nào cắt đường chéo nối bởi đỉnh của ngọn núi $i$ và đỉnh của ngọn núi $j$. Nói cách khác, với hai ngọn núi $i < j$ có thể nhìn thấy nhau nếu không tồn tại ngọn núi $k$ thoả mãn $i < k < j$ và điểm $(k, h_k)$ nằm bên trên đoạn thẳng tạo bởi hai điểm $(i, h_i)$ và $(j, h_j)$. Có $Q$ $(1 \le Q \le 2000)$ lần cập nhật độ cao, trong đó, mỗi lần cập nhật sẽ làm tăng cao của một ngọn núi. Tìm tổng số lượng các cặp có thể nhìn thấy nhau sau mỗi lần cập nhật (Cặp $(i, j)$ và $(j, i)$ được coi là như nhau).

Input

Dòng $1$ là số $N$.
Dòng $2$ là $N$ số $h_1, h_2, \dots, h_n$ ($\forall i, 0 \le h_i \le 10^9$).
Dòng $3$ là số $Q$.
Từ dòng $4$ đến dòng $Q + 3$, mỗi dòng gồm $2$ số $x$ và $y$ $(1 \le x \le N, 1 \le y)$, trong đó $x$ là vị trí của ngọn núi sẽ thay đổi độ cao và $y$ là lượng mà độ cao của ngọn núi này tăng thêm $(h_x = h_x + y)$. Dữ liệu đảm bảo độ cao mới của ngọn núi không vượt quá $10^9$.

Output

$Q$ dòng, mỗi dòng là số lượng các cặp thoả mãn đề bài.

Scoring

Subtask $1$: $N, Q \le 100$.
Subtask $2$: $Q \le 10$.
Subtask $3$: Không có thêm ràng buộc.

Test 1

Input

Output

7
10
7

Note

Ban đầu, có $6$ cặp ngọn núi có thể nhìn thấy nhau: $(1, 2), (2, 3), (2, 5), (3, 4), (3, 5), (4, 5)$.
Sau lần cập nhật đầu tiên, độ cao mới của ngọn núi $4$ là $4$, các cặp ngọn núi có thể nhìn thấy nhau cũ không bị ảnh hưởng và ngọn núi $4$ bây giờ có thể nhìn thấy ngọn núi $2$, do đó đáp án là $7$.
Sau lần cập nhật thứ $2$, ngọn núi $1$ có độ cao là $5$, cũng không ảnh hưởng đến các cặp cũ và ngọn núi $1$ bây giờ có thể nhìn thấy ngọn núi $3, 4$ và $5$, do đó đáp án là $10$.
Sau lần cập nhật cuối cùng, ngọn núi $3$ có độ cao là $5$, ngăn ngọn núi $1$ thấy ngọn núi $4$, ngọn núi $2$ thấy ngọn núi $4$ và $5$ và ngọn núi $3$ cũng không thấy thêm ngọn núi nào cả, do đó đáp án là $7$.

3. USACO 2022 December Contest, Gold, Strongest Friendship Group

Điểm: 100 (p) Thời gian: 2.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Nông dân John có $N$ con bò $(2 \le N \le 10^5)$, được đánh số $1 \dots N$. Có $M$ $(1 \le M \le 2 \times 10^5)$ cặp bạn bè giữa những chú bò này.

Một nhóm bò được gọi "nhóm bạn thân" nếu như giữa hai chú bò bất kì đều có thể quen nhau thông qua một chuỗi các cặp bạn bè cùng nằm trong nhóm (tình bạn với các chú bò ngoài nhóm không có ảnh hưởng gì). "Sức mạnh" của một nhóm bạn bè là số lượng bạn bè ít nhất của chú bò bất kì nhân với số lượng bò trong nhóm (lần nữa, bạn bè ngoài nhóm không được tính nhé!!).

Tính sức mạnh lớn nhất trong tất cả các nhóm bạn thân.

Input

Dòng đầu tiên gồm hai số $N$ và $M$.
$M$ dòng tiếp theo là $2$ số $u_i, v_i$ thể hiện rằng chú bò $u_i$ là bạn với chú bò $v_i$ $(1 \le u_i, v_i \le N, u_i \ne v_i)$. Không có cặp nào xuất hiện quá một lần.

Output

Gồm một dòng là sức mạnh lớn nhất trong tất cả các nhóm bạn thân.

Scoring

Subtask $1$: $N \le 16$.
Subtask $2$: $N \le 1000$.
Subtask $3$: Không có ràng buộc gì thêm.

Test 1

Input

Output

Note

Sức mạnh lớn nhất có thể đạt được là của nhóm bò gồm $1$, $2$, $3$, $4$. Mọi chú bò đều có ít nhất $3$ bạn trong nhóm nên đáp án là $3 \times 4 = 12$.