Ôn tập HSG Olympic 30/4 - Ngày 1

Trong thời kì loạn lạc của LQDOJ conghieupt2555 là \(1\) trong nhưng chiến binh tài năng. Đang thách đấu với PhuocThien cũng là \(1\) chiến binh rất mạnh khác. Hôm nay để dành được ngôi bá chủ LQDOJ họ đã thách đấu với nhau. Ở trận này họ quyết định đấu bằng thuật toán.
conghieupt2555 đưa ra số nguyên dương \(N\) là sức mạnh của anh ấy.
PhuocThien biết trong sức mạnh đó có tồn tại các phần tử là điểm yếu của conghieupt2555. Chỉ cần đánh đúng vào tất cả các điểm đó thì PhuocThien sẽ chiến thắng.
Biết điểm đó là các số nguyên dương nhỏ hơn hoặc bằng \(N\) có số lượng ước là \(2\).
Hãy giúp PhuocThien đánh bại conghieupt2555 trong trận đấu này nhé!

Input

• Một số nguyên \(N\) là sức mạnh của conghieupt2555. \((1 \le N \le 10^7)\)

Output

• In ra các số nguyên dương là điểm yếu của conghieupt2555 theo thứ tự từ bé đến lớn.

Example

5

2 3 5

Trong quá trình nghiên cứu, PhuocThien phát hiện rằng mỗi con số \(x\) đều mang một “sức mạnh ẩn” chính là số lượng ước số của nó.

Bạn được cho một số \(N\) và \(Q\) truy vấn.
Mỗi truy vấn yêu cầu tính tổng số lượng ước của các số trong đoạn \([L, R]\).

Input

• Dòng 1: hai số \(N, Q\) \((1 \le N \le 10^6,\ 1 \le Q \le 2 \cdot 10^5)\).
• \(Q\) dòng tiếp theo, mỗi dòng chứa hai số \(L, R\) \((1 \le L \le R \le N)\).

Output

• Với mỗi truy vấn, in ra một số nguyên là: \(\sum_{i=L}^{R} d(i)\), trong đó \(d(i)\) là số lượng ước của \(i\).

Ví dụ

5 2
1 3
2 5

5
9

Ràng buộc

• \(1 \le N \le 10^6\).
• \(1 \le Q \le 2 \cdot 10^5\).

Scoring

• Subtask \(1\) (\(30\%\)): \(N \le 10^5\).
• Subtask \(2\) (\(70\%\)): Không có ràng buộc thêm.

Trong thế giới LQDOJ cấp cao nơi thuật toán quyết định mọi thứ, PhuocThien đã nâng cấp hệ thống từ dãy một chiều lên ma trận năng lượng kích thước \(n \times m\), nhưng chính điều này đã mở ra điểm yếu chí mạng khiến hệ thống dễ bị tấn công hơn bao giờ hết. Ngay khi phát hiện ra điều đó, hai đối thủ nguy hiểm conghieupt2555 và hbl lập tức khai thác triệt để và bắt đầu tung ra các đòn “phủ vùng” cực kỳ phức tạp lên toàn bộ ma trận. Không còn những thao tác đơn giản theo đoạn, mỗi đòn tấn công giờ đây ảnh hưởng theo cả hai chiều, tạo thành những vùng biến đổi lan rộng khó kiểm soát.
Mỗi đòn tấn công có dạng \((x_1, y_1, x_2, y_2, k)\) và với mọi ô \((i, j)\) thỏa mãn \(x_1 \le i \le x_2\) và \(y_1 \le j \le y_2\) thì giá trị bị thay đổi theo công thức \(a_{i,j} = a_{i,j} + (i - x_1 + 1)\cdot (j - y_1 + 1)\cdot k\). Điều này đồng nghĩa mỗi đòn tạo ra một “ma trận tăng trưởng” mà giá trị không chỉ tăng theo hàng mà còn tăng theo cột, khiến tốc độ biến đổi trở nên cực kỳ nhanh. Các đòn tấn công chồng chéo lên nhau tạo thành những vùng nhiễu loạn phức tạp khiến việc mô phỏng trực tiếp gần như không khả thi trong giới hạn thời gian.
PhuocThien buộc phải tìm ra cách tính toán chính xác trạng thái cuối cùng của toàn bộ ma trận sau khi tất cả các đòn tấn công kết thúc, nếu không toàn bộ hệ thống sẽ sụp đổ do sai lệch dữ liệu tích lũy.

Input

• Dòng đầu tiên chứa ba số nguyên \(n, m, q\).
• \(n\) dòng tiếp theo, mỗi dòng chứa \(m\) số nguyên \(a_{i,j}\) (\(1 \le n, m \le 1000\), \(|a_{i,j}| \le 10^9\)).
• \(q\) dòng tiếp theo, mỗi dòng gồm năm số \(x_1, y_1, x_2, y_2, k\) (\(1 \le x_1 \le x_2 \le n\), \(1 \le y_1 \le y_2 \le m\), \(|k| \le 10^4\), \(q \le 10^5\)).

Output

• In ra ma trận sau khi tất cả các đòn tấn công kết thúc, mỗi dòng gồm \(m\) số.

Example

2 2 1
1 1
1 1
1 1 2 2 1

2 3
3 5

2 3 1
0 0 0
0 0 0
1 2 2 3 2

0 2 4
0 4 8

Scoring

• Subtask \(1\) (\(50\%\) điểm): \(1 \le n, m \le 300\), \(q \le 5000.\)
• Subtask \(2\) (\(50\%\) điểm): \(1 \le n, m \le 1000\), \(q \le 10^5.\)

Trong khu rừng cổ, PhuocThien phát hiện một cổ thụ thần có bộ rễ nối thành một cây gồm \(n\) đỉnh. Mỗi đỉnh mang một chỉ số sinh mệnh. Khi cổ thụ hấp thụ ánh sáng, năng lượng không lan đều mà chỉ truyền theo những nhánh đủ “điều kiện cộng hưởng”.

DatthicTech và conghieupt2555 biết được bí mật ấy nên đã đặt lên cây một chuỗi nghi thức.
Mỗi nghi thức chọn một đỉnh \(u\) làm gốc, rồi yêu cầu xét toàn bộ các đỉnh trong cây con của \(u\) theo cây đã được cố định gốc tại đỉnh \(1\).

Với một nghi thức tại đỉnh \(u\), PhuocThien có thể chọn đúng \(k\) đỉnh bất kỳ trong cây con của \(u\), nhưng các đỉnh được chọn phải tạo thành một tập liên thông. Giá trị của một tập được tính bằng tổng sinh mệnh của các đỉnh trong tập đó.

Nhiệm vụ của bạn là với mỗi đỉnh \(u\), hãy tìm giá trị lớn nhất của một tập gồm đúng \(k\) đỉnh, liên thông và nằm hoàn toàn trong cây con của đỉnh \(u\).

Input

• Dòng đầu tiên chứa hai số nguyên \(n, k\) \((1 \le n \le 5000,\ 1 \le k \le min(n, 200))\).
• Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, \dots, a_n\) \((-10^9 \le a_i \le 10^9)\) — chỉ số sinh mệnh của các đỉnh.
• \(n-1\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(u, v\) \((1 \le u, v \le n)\), mô tả một cạnh của cây.

Cây được gốc hóa tại đỉnh \(1\).

Output

In ra \(n\) dòng.
Dòng thứ \(u\) chứa một số nguyên là giá trị lớn nhất của một tập gồm đúng \(k\) đỉnh, liên thông và nằm trong cây con của đỉnh \(u\).
Nếu không tồn tại tập như vậy, in ra -1.

Example

5 3
3 1 -2 4 2
1 2
1 3
2 4
2 5

8
7
-1
-1
-1

4 2
-5 10 -1 7
1 2
2 3
3 4

9
9
6
-1

Scoring

• Subtask \(1\) (\(25\%\)): \(n \le 200\), \(k \le 20\).
• Subtask \(2\) (\(35\%\)): Cây là đường thẳng.
• Subtask \(3\) (\(40\%\)): Không có ràng buộc thêm.

Sau chuyến đi đầu tiên trong phần \(1\), PhuocThien cùng DatthicTech, KimHieu, conghieupt2555 và vov đã mang về được rất nhiều món đồ kỷ niệm từ các điểm dừng chân trên hành trình 30/4. Có món là một chiếc huy hiệu nhỏ, có món là một bức ảnh chụp vội bên đường, có món là một mảnh giấy ghi chú do cả nhóm trao nhau trên xe, và cũng có món là những vật phẩm đặc biệt chỉ xuất hiện ở đúng một nhánh của chuyến đi. Ban đầu, PhuocThien nghĩ chỉ cần gom tất cả vào một chiếc túi duy nhất là xong, nhưng rất nhanh anh nhận ra chiếc túi này không hề đơn giản như tưởng tượng: mỗi vật phẩm đều có trọng lượng, giá trị riêng, và còn thuộc về một nhóm hành trình khác nhau. Nếu sắp xếp không khéo, chiếc túi sẽ bị lấp đầy bởi những món đồ nặng nhưng không thật sự hữu ích, khiến giá trị kỷ niệm cuối cùng thấp hơn rất nhiều so với tiềm năng thật sự của chuyến đi.

DatthicTech là người đầu tiên nêu ý kiến rằng chỉ cần chọn những món đồ có giá trị lớn nhất trước là được, nhưng KimHieu phản bác ngay lập tức. Trong những tình huống như thế này, món đồ tốt nhất không phải lúc nào cũng là món có giá trị lớn nhất, mà là món giúp mở ra nhiều lựa chọn hơn cho phần còn lại của túi. Một món vật phẩm nhẹ hơn có thể cho phép mang thêm hai món khác, và đôi khi tổng giá trị cuối cùng lại vượt xa một món đồ rất đắt nhưng chiếm quá nhiều chỗ. vov thì nhận xét rằng đây chính là kiểu bài toán không thể giải bằng cảm tính, vì số phương án tăng quá nhanh khi số lượng vật phẩm lớn dần. Nếu kiểm tra từng tập con, chuyến đi sẽ kết thúc trước khi lời giải xuất hiện.

Nhìn lại toàn bộ chiến lợi phẩm của chuyến đi, PhuocThien phát hiện ra một quy luật quan trọng: các vật phẩm không chỉ có trọng lượng và giá trị, mà còn được gắn với một mã nhóm \(c_i\). Mọi vật phẩm có cùng mã nhóm đều thuộc cùng một cụm hành trình, tức là chúng được tạo ra từ cùng một đoạn đường hoặc cùng một kỷ niệm đặc biệt. Điều này khiến bài toán không còn là chiếc túi bình thường nữa, mà trở thành một bài toán quy hoạch động có cấu trúc nhóm. Mỗi nhóm có thể gồm nhiều vật phẩm, và việc chọn trong một nhóm sẽ ảnh hưởng trực tiếp đến khả năng chọn ở các nhóm khác vì tổng sức chứa của túi là hữu hạn. PhuocThien hiểu rằng nếu không xử lý theo đúng thứ tự, anh sẽ bị mắc kẹt trong hàng loạt phương án trùng lặp và không thể tìm ra lời giải tối ưu.

conghieupt2555 đề nghị rằng nên ghép các vật phẩm theo nhóm rồi xử lý lần lượt từng nhóm như những khối độc lập, còn DatthicTech cho rằng nên thử mọi khả năng trong từng nhóm trước rồi mới đưa vào trạng thái chung của chiếc túi. Sau một thời gian bàn bạc, cả nhóm thống nhất rằng đây chính là dạng bài kinh điển của quy hoạch động cái túi, nhưng có thêm một tầng nhóm đặc biệt: Trong mỗi nhóm hành trình, bạn chỉ được phép chọn tối đa một vật phẩm để mang theo, không được kết hợp nhiều vật phẩm từ cùng một nhóm vào túi. Mỗi lần ghép một nhóm mới, các trạng thái cũ phải được giữ lại cẩn thận, vì có thể phương án tốt nhất ở nhóm sau lại phụ thuộc vào việc nhóm trước đã dùng bao nhiêu dung lượng.

Điều làm bài toán này trở nên thú vị là ở chỗ nó không chỉ kiểm tra khả năng tối ưu hóa, mà còn kiểm tra khả năng tổ chức thông tin. KimHieu nói rằng nếu xem mỗi nhóm hành trình như một câu chuyện nhỏ, thì nhiệm vụ của người giải là phải biết chọn những câu chuyện nào đáng để đưa vào chiếc túi sao cho tổng giá trị cảm xúc cao nhất. Có những nhóm chỉ có một vật phẩm rất mạnh, có những nhóm lại có nhiều vật phẩm nhỏ nhưng ghép với nhau thì cực kỳ hiệu quả, và có những nhóm gần như chỉ để "đánh lạc hướng" người giải bằng các phương án tưởng đẹp nhưng lại không tối ưu. vov thì nhắc rằng một lời giải tốt phải vừa đúng, vừa gọn, vừa đủ nhanh để xử lý toàn bộ dữ liệu trong giới hạn cho phép.

Nhiệm vụ của bạn là thay PhuocThien hoàn thiện chiếc túi đặc biệt ấy. Hãy chọn một tập vật phẩm sao cho tổng trọng lượng không vượt quá giới hạn của túi \(W\), đồng thời thỏa mãn quy tắc nhóm hành trình: từ mỗi nhóm, bạn chỉ được chọn tối đa một vật phẩm duy nhất (hoặc không chọn vật phẩm nào từ nhóm đó). Việc xét chọn phải được thực hiện theo đúng cấu trúc nhóm để tối đa hóa tổng giá trị kỷ niệm. Mục tiêu cuối cùng là tối đa hóa tổng giá trị của các vật phẩm đã chọn. Nếu có nhiều cách chọn cho cùng một giá trị lớn nhất, chỉ cần in ra giá trị đó.

Input

• Dòng đầu tiên chứa hai số nguyên \(n, W\) \((1 \le n \le 2000,\ 1 \le W \le 10^5)\).
• \(n\) dòng tiếp theo, mỗi dòng chứa ba số nguyên \(w_i, v_i, c_i\) trong đó:
• \(w_i\) là trọng lượng của vật phẩm thứ \(i\),
• \(v_i\) là giá trị của vật phẩm thứ \(i\),
• \(c_i\) là mã nhóm hành trình của vật phẩm thứ \(i\).
• Hai vật phẩm có cùng mã \(c_i\) thuộc cùng một nhóm.

Output

In ra một số nguyên duy nhất là tổng giá trị lớn nhất có thể đạt được mà không vượt quá sức chứa \(W\).

Ràng buộc

• \(1 \le n \le 2000\).
• \(1 \le W \le 10^5\).
• \(1 \le w_i \le W\).
• \(1 \le v_i \le 10^9\).
• \(1 \le c_i \le n\).

Example

5 10
3 6 1
4 7 1
5 9 2
2 4 2
6 10 3

17

Scoring

• Subtask \(1\) (\(50\%\) điểm): \(n \le 200\), \(W \le 2000\).
• Subtask \(2\) (\(50\%\) điểm): Không có ràng buộc thêm.