CEOI 2017 - Day 2

Có \(n\) cây cột đứng trên sông, xếp thành một hàng thẳng từ bờ này sang bờ kia. Chiều cao cột thứ \(i\) là \(h_i\). Ta muốn xây một cây cầu được đỡ bởi một số cột đã chọn; cột đầu tiên và cột cuối cùng bắt buộc phải được chọn. Nối đỉnh của mỗi cặp cột được chọn liên tiếp bằng một đoạn cầu.

Chi phí xây đoạn cầu nối cột \(i\) và cột \(j\) là \((h_i-h_j)^2\). Ngoài ra, mọi cột không được chọn phải bị dỡ bỏ để không cản trở giao thông trên sông. Chi phí dỡ cột thứ \(i\) là \(w_i\); giá trị này có thể âm vì có bên sẵn sàng trả tiền để cột bị dỡ.

Hãy chọn các cột làm trụ cầu sao cho tổng chi phí xây cầu và dỡ các cột còn lại là nhỏ nhất.

Dữ liệu vào

Dòng đầu chứa số nguyên \(n\) (\(2\le n\le100000\)), là số cột.

Dòng thứ hai chứa \(n\) số nguyên \(h_i\) (\(0\le h_i\le10^6\)), là chiều cao các cột theo thứ tự.

Dòng thứ ba chứa \(n\) số nguyên \(w_i\) (\(-10^6\le w_i\le10^6\)), là chi phí dỡ từng cột.

Dữ liệu ra

In một số nguyên duy nhất là tổng chi phí nhỏ nhất. Kết quả có thể âm.

Ví dụ

6
3 8 7 1 6 6
0 -1 9 1 2 0

17

Phân nhóm

1. \(30\) điểm: \(n\le1000\).
2. \(30\) điểm: Phương án tối ưu có nhiều nhất \(2\) cột trụ bổ sung ngoài cột đầu và cột cuối; \(|w_i|\le20\).
3. \(40\) điểm: Không có ràng buộc bổ sung.

Phân hoạch một xâu là cách chia xâu thành một hoặc nhiều xâu con liên tiếp, không rỗng và đôi một không giao nhau, sao cho ghép chúng theo thứ tự ban đầu sẽ thu lại xâu gốc. Gọi mỗi xâu con là một khối; độ dài của phân hoạch là số khối.

Một phân hoạch được gọi là đối xứng nếu dãy các khối tạo thành một palindrome khi xem mỗi khối như một phần tử không thể chia nhỏ. Ví dụ, xâu decode có các phân hoạch đối xứng (de)(co)(de) và (decode). Mọi xâu đều có phân hoạch đối xứng tầm thường chỉ gồm một khối.

Với mỗi xâu được cho, hãy tìm số khối lớn nhất có thể trong một phân hoạch đối xứng.

Dữ liệu vào

Dòng đầu chứa số nguyên \(t\) (\(1\le t\le10\)), là số bộ kiểm thử.

Mỗi dòng trong \(t\) dòng tiếp theo chứa một xâu \(s\) chỉ gồm các chữ cái tiếng Anh viết thường. Gọi \(n\) là độ dài của xâu \(s\); ta có \(1\le n\le10^6\).

Dữ liệu ra

Với mỗi bộ kiểm thử, in một dòng chứa số khối lớn nhất của một phân hoạch đối xứng.

Ví dụ

4
bonobo
deleted
racecar
racecars

3
5
7
1

Phân nhóm

1. \(15\) điểm: \(n\le30\).
2. \(20\) điểm: \(n\le300\).
3. \(25\) điểm: \(n\le10000\).
4. \(40\) điểm: Không có ràng buộc bổ sung.

Tom lại đuổi theo Jerry. Jerry muốn tạo lợi thế bằng cách chạy qua những đám chim bồ câu, nơi Tom khó đuổi theo hơn. Jerry đang ở công viên trung tâm Ljubljana, nơi có \(n\) bức tượng đánh số từ \(1\) đến \(n\), nối với nhau bằng \(n-1\) lối đi sao cho có thể đi từ tượng bất kỳ đến mọi tượng khác. Quanh tượng thứ \(i\) có \(p_i\) con chim bồ câu.

Jerry có \(v\) mẩu bánh mì. Khi đến tượng \(i\), trước tiên Jerry gặp số chim hiện có tại đó. Sau đó, nếu muốn, anh có thể thả một mẩu bánh mì. Tất cả chim ở các tượng kề với \(i\) lập tức bay đến tượng \(i\): số chim tại \(i\) tăng thêm tổng số chim ở các tượng kề, còn các tượng kề đó không còn chim. Jerry rời tượng. Việc chim di chuyển xảy ra trước khi Jerry đến tượng tiếp theo, nên số chim vừa bay đến không được tính vào số chim Jerry gặp tại tượng \(i\).

Jerry có thể bắt đầu ở bất kỳ tượng nào, đi qua các lối (không bao giờ đi qua cùng một lối hai lần), rồi rời công viên tại bất kỳ tượng nào. Anh được thả nhiều nhất \(v\) mẩu bánh mì. Sau khi Jerry rời công viên, Tom đi theo đúng tuyến đường đó. Hãy tối đa hóa hiệu giữa tổng số chim Tom gặp và tổng số chim Jerry gặp.

Dữ liệu vào

Dòng đầu chứa hai số nguyên \(n,v\) (\(1\le n\le100000\), \(0\le v\le100\)), lần lượt là số tượng và số mẩu bánh mì.

Dòng thứ hai chứa \(n\) số nguyên \(p_1,p_2,\ldots,p_n\) (\(0\le p_i\le10^9\)), là số chim ban đầu quanh mỗi tượng.

Mỗi dòng trong \(n-1\) dòng tiếp theo chứa hai số nguyên \(a_i,b_i\) (\(1\le a_i,b_i\le n\)), cho biết có lối đi giữa hai tượng \(a_i\) và \(b_i\).

Dữ liệu ra

In một số nguyên duy nhất là hiệu lớn nhất có thể đạt được.

Ví dụ

12 2
2 3 3 8 1 5 6 7 8 3 5 4
2 1
2 7
3 4
4 7
7 6
5 6
6 8
6 9
7 10
10 11
10 12

36

Giải thích

Jerry có thể bắt đầu tại tượng \(6\), gặp \(5\) con chim rồi thả một mẩu bánh mì. Khi đó tượng \(6\) có \(27\) con chim, còn các tượng \(5,7,8,9\) không còn chim. Sau đó Jerry đi đến tượng \(7\), gặp \(0\) con chim rồi thả mẩu bánh mì thứ hai. Tượng \(7\) có \(41\) con chim, còn các tượng \(2,4,6,10\) không còn chim. Jerry rời công viên. Jerry gặp tổng cộng \(5+0=5\) con chim; Tom đi theo cùng tuyến đường và gặp \(0+41=41\) con. Hiệu là \(41-5=36\).

Phân nhóm

1. \(20\) điểm: \(n\le10\).
2. \(20\) điểm: \(n\le1000\).
3. \(30\) điểm: Có một phương án tối ưu bắt đầu tại tượng \(1\).
4. \(30\) điểm: Không có ràng buộc bổ sung.