Bài tập

Các nhà máy sản xuất các thiết bị của tập đoàn Space X thường được đặt ở những vùng đất đặc biệt. Nhà máy sản xuất các mảnh ghép được xây dựng trên một vùng diện tích có dạng hình chữ nhật \(m\times n\) bằng cách xếp chồng các khối vật liệu lên nhau, khối vật liệu là một khối lập phương đơn vị có kích thước \((1\times1\times1)\). Các khối vật liệu của nhà máy được chế tạo từ hợp kim vững chắc để chống chịu các tác động của thiên tai khắc nghiệt. Khi kết thúc hoạt động của nhà máy, tập đoàn phải phá hủy nhà máy để trả lại nguyên trạng vùng đất ban đầu. Để làm được điều đó, tập đoàn phải phá hủy các khối vật liệu ban đầu được dùng để xây dựng nhà máy; các khối vật liệu được phá hủy bằng cách bắn tia laser vào nó.

Máy bắn tia laser được lắp đặt ở bốn phía của nhà máy, và chúng được thiết lập để bắn tia laser vào một số khối vật liệu của nhà máy (tia laser luôn vuông góc với các mặt của nhà máy). Mỗi tia laser phá hủy \(r\) khối đầu tiên trên đường đi của nó. Nếu có một hoặc nhiều khối trên đỉnh của khối bị phá hủy, chúng sẽ di chuyển thẳng xuống. Sau khi bắn \(k\) tia laser, tập đoàn quyết định thực hiện một cuộc phá hủy trên diện rộng. Họ quyết định chọn khu vực có kích thước \(p\times p\) trên nhà máy sao cho số lượng khối vật liệu bị phá hủy là nhiều nhất có thể; các tia laser sẽ được bố trí phù hợp để phá hủy tất cả các khối vật liệu trong khu vực này.

Tìm số lượng khối vật liệu tối đa bị phá hủy trong khu vực có kích thước \(p\times p\) sau khi thực hiện \(k\) phát bắn.

Input

Cho trong file CLEAN.INP, có cấu trúc:

• Dòng 1: Chứa năm số nguyên \(m,n,r,k,p\).

• Trên \(m\) dòng tiếp theo: Mỗi dòng chứa \(n\) số; số \(a_{i,j}\) ở dòng thứ \(i\), cột thứ \(j\) là số khối lập phương đơn vị được xếp chồng lên nhau ở vị trí \((i,j)\) \((1 \le a_{i,j} \le 10^6)\).
• Trên \(k\) dòng tiếp theo mô tả các phát bắn laser, có dạng dir i h:
• dir là một trong bốn chữ cái, mô tả hướng bắn: W — hướng Tây, E — hướng Đông, S — hướng Nam, N — hướng Bắc.
• \(i\) là một số nguyên dương. Nếu hướng bắn là hướng Đông hoặc hướng Tây thì đây là chỉ số dòng; nếu hướng bắn là hướng Nam hoặc hướng Bắc thì đây là chỉ số cột bị bắn \((1 \le i \le 10^6)\).
• \(h\) là độ cao của phát bắn \((1 \le h \le 10^6)\).

Output

Ghi ra file CLEAN.OUT:

• Dòng 1: Ghi một số nguyên duy nhất là kết quả bài toán.

Example

Scoring

• 30% số test ứng với 30% số điểm có \(n\times m \le 300\).
• 70% số test ứng với 70% số điểm không có ràng buộc gì thêm.

Với sự hỗ trợ tuyệt vời của các bạn trong đội dự tuyển, các dự án của Mark đã thực hiện một cách hoàn hảo và nhanh chóng. Để tỏ lòng cảm ơn, Mark muốn mời các bạn cùng tham gia buổi triển lãm công nghệ vũ trụ thường niên của tập đoàn. Các bạn rất háo hức và mong muốn được cống hiến một chút sức mình vào buổi triển lãm. Mark giới thiệu như sau:

Trong sự kiện triển lãm năm nay, điểm nhấn của sự kiện chính là phần trình diễn robot kết hợp với hiệu ứng đèn LED cực kỳ hấp dẫn. Có \(n\) robot với chiều cao khác nhau từng đôi một, được xếp thành một hàng để đi qua sân khấu trung tâm.

Để có hiệu ứng đèn LED đẹp nhất, Mark yêu cầu như sau: khán giả ở khán đài phía Tây (bên trái hàng diễu hành) có thể nhìn thấy đúng \(p\) robot. Khán giả ở khán đài phía Đông (bên phải hàng diễu hành) có thể nhìn thấy đúng \(q\) robot.

Một robot được gọi là “nhìn thấy” từ một phía nếu tất cả các robot phía trước nó theo hướng nhìn đều thấp hơn nó. Ví dụ: Với 9 robot có chiều cao được xếp thành hàng: \(3,2,4,1,9,8,7,5,6\):

• Từ khán đài phía Tây, khán giả thấy được 3 robot (chiều cao 3, 4, 9).
• Từ khán đài phía Đông, khán giả thấy được 4 robot (chiều cao 6, 7, 8, 9).

Hãy giúp CEO Mark xác định xem có bao nhiêu cách xếp \(n\) robot thành một hàng thỏa mãn điều kiện đặt ra.

Input

Cho trong file ROBOT.INP, có cấu trúc:

• Dòng 1: Chứa ba số nguyên dương \(n,p,q\) \((1 \le n \le 2000;\ 1 \le p,q \le n)\).
• Dòng 2: Chứa \(n\) số nguyên dương \(a_1,a_2,a_3,\ldots,a_n\) là các độ cao của \(n\) robot \((1 \le a_i \le 2000)\).

Các số trên cùng một dòng được ghi cách nhau ít nhất một dấu cách.

Output

Ghi ra file ROBOT.OUT:

• Dòng 1: Ghi một số nguyên là phần dư trong phép chia số lượng cách xếp tìm được cho \(10^9+7\).

Example

3 2 1
1 2 3

1

Scoring

• 25% số test ứng với 25% số điểm có \(n \le 10\).
• 25% số test ứng với 25% số điểm có \(n \le 500, q=1\).
• 25% số test ứng với 25% số điểm có \(n \le 500\).
• 25% số test ứng với 25% số điểm có \(n \le 2000\).

Hôm nay chúng ta lại bắt đầu một ngày làm việc bận rộn của Mark — một CEO của tập đoàn Space X. Thử thách cho các bạn hôm nay đó là phân công công việc cho các nhân viên sao cho hiệu quả nhất. Thông tin cụ thể như sau, tập đoàn có \(n\) dự án cần hoàn thành, được đánh số từ \(1\) đến \(n\). Mỗi dự án có một giá trị là lợi nhuận thu được sau khi thực hiện dự án thứ \(i\), gọi là \(a_i\).

Hiện tại, tập đoàn phân bổ \(k\) nhân viên để thực hiện một số dự án. Để thuận tiện cho khâu quản lý, mỗi nhân viên chỉ có thể nhận một số dự án liên tiếp nhau, tức là một nhân viên có thể nhận một hoặc nhiều dự án liền kề, và mỗi dự án chỉ được giao cho một nhân viên. Một số dự án không có lợi nhuận hoặc thua lỗ có thể không được giao cho bất kỳ nhân viên nào.

Mục tiêu của tập đoàn là phân công các dự án cho các nhân viên sao cho tổng giá trị lợi nhuận các dự án mà nhân viên thực hiện là cao nhất có thể. Tổng giá trị công việc mà mỗi nhân viên thực hiện được tính bằng tổng giá trị các dự án mà người đó đảm nhiệm; nếu nhân viên không nhận dự án nào thì giá trị bằng 0.

Các bạn hãy tìm cách phân chia các dự án cho các nhân viên sao cho tổng lợi nhuận các dự án mà tất cả các nhân viên thực hiện là lớn nhất.

Input

Cho trong file PLAN.INP, có cấu trúc:

• Dòng 1: Chứa hai số nguyên dương lần lượt \(n,k\) \((1 \le n \le 2000)\).
• Dòng 2: Chứa \(n\) số nguyên \(a_1,a_2,\ldots,a_n\) \((|a_i| \le 10^9)\).

Các số trên cùng một dòng được ghi cách nhau ít nhất một dấu cách.

Output

Ghi ra file PLAN.OUT:

• Dòng 1: Ghi một số nguyên là tổng lợi nhuận lớn nhất.

Example

5 1
1 -2 3 -1 4

6

5 2
1 -2 3 -1 4

7

Scoring

• Có \(1/3\) số điểm tương ứng với \(1 \le n \le 80\).
• Có \(1/3\) số điểm tương ứng với \(81 \le n \le 300\).
• Có \(1/3\) số điểm tương ứng với \(301 \le n \le 2000\).

Cho một đồ thị vô hướng có dạng cây, tức là đồ thị gồm \(n\) đỉnh và \(n-1\) cạnh. Các đỉnh được đánh số từ \(1\) đến \(n\), đỉnh thứ \(i\) có trọng số là \(w_i\).

Ví dụ, ta có một cây với gốc là 1:

• Cây gốc 1 bao gồm các đỉnh \(\{1,2,3,4,5,6,7\}\).
• Cây con có gốc là 2 bao gồm các đỉnh \(\{2,6,5,4\}\).
• Cây con có gốc là 3 bao gồm các đỉnh \(\{3,7\}\).

Ta định nghĩa \(S(\mathrm{root},a)\) là tổng trọng số của các đỉnh trong cây con có gốc \(a\), khi cây được định nghĩa với gốc là \(\mathrm{root}\), tức là:

Bạn hãy trả lời \(q\) truy vấn, mỗi truy vấn thuộc một trong hai dạng sau:

1. Truy vấn loại 1: 1 a b — Ghi ra giá trị \(S(a,b)\).
2. Truy vấn loại 2: 2 a b v — Chọn gốc của cây là \(a\), và cập nhật trọng số của các đỉnh \(u\) thuộc cây con có gốc \(b\) theo phép XOR với \(v\), tức là:

với \(\oplus\) là phép bitwise XOR trong C++.

Input

Cho trong file TREEQUERY.INP, có cấu trúc:

• Dòng 1: Chứa số nguyên \(n\), là số đỉnh của cây \((1 \le n \le 10^5)\).
• Dòng 2: Chứa \(n\) số nguyên \(w_1,w_2,\ldots,w_n\), là trọng số các đỉnh \((0 \le w_i \le 10^9)\).
• Trên \(n-1\) dòng tiếp theo: Mỗi dòng chứa hai số nguyên \(u,v\) biểu diễn một cạnh giữa đỉnh \(u\) và đỉnh \(v\) của cây \((1 \le u,v \le n)\).
• Dòng tiếp theo chứa số nguyên \(q\), là số truy vấn \((1 \le q \le 10^5)\).
• Trên \(q\) dòng tiếp theo, mỗi dòng biểu diễn một truy vấn:
• Truy vấn loại 1: 1 a b \((1 \le a,b \le n)\) — Ghi ra \(S(a,b)\).
• Truy vấn loại 2: 2 a b v \((1 \le a,b \le n,\ 1 \le v \le 10^9)\) — Cập nhật trọng số các đỉnh trong cây con gốc \(b\) khi cây có gốc \(a\), theo phép XOR với \(v\).

Output

Ghi ra file TREEQUERY.OUT:

• Với mỗi truy vấn loại 1, ghi ra một dòng là kết quả \(S(a,b)\).

Example

7
1 2 3 4 5 6 7
1 2
1 3
2 4
2 6
3 7
6 5
3
1 1 2
2 1 2 1
1 1 2

17
19

Chú ý: Thời gian thực hiện chương trình tối đa cho mỗi bộ test bất kỳ là không quá 01 giây.

Scoring

• 20% số test tương ứng với 20% số điểm của bài có \(n,q \le 2000\).
• 20% số test tương ứng với 20% số điểm của bài không có truy vấn loại 2.
• 20% số test tương ứng với 20% số điểm ứng với trường hợp mỗi đỉnh trên cây có tối đa hai đỉnh kề với nó.
• 20% số test tương ứng với 20% số điểm của bài không có \(a=1\).
• 20% số test còn lại tương ứng với 20% số điểm của bài không có ràng buộc gì thêm.