Một số bài hơi random

Để chào mừng cuộc thi Olympic 30/4, Hạnh nhận nhiệm vụ trang trí băng rôn chào mừng. Ban đầu, băng rôn là một chuỗi có chiều dài \(n\) chỉ gồm các chữ cái in hoa O, L và P. Một băng rôn được gọi là “đẹp” nếu có chứa một trong các kí tự O, L hoặc P với số lần xuất hiện từ \(3\) trở lên.

Yêu cầu: Cho xâu \(S\) là nội dung của băng rôn ban đầu, hãy đếm số lượng xâu con thỏa điều kiện là băng rôn “đẹp”.

Input

• Một dòng duy nhất chứa xâu \(S\) độ dài \(n\) \((3 \leq n \leq 10^{5})\) chỉ gồm các chữ cái O, L, P.

Output

• Một số nguyên duy nhất là số lượng xâu con thỏa điều kiện là băng rôn “đẹp”.

Scoring

• Subtask \(1\) (\(25\%\) điểm): \(3 \leq n \leq 10^{2}\).
• Subtask \(2\) (\(25\%\) điểm): \(10^{2} < n \leq 10^{3}\).
• Subtask \(3\) (\(50\%\) điểm): \(10^{3} < n \leq 10^{5}\).

Example

OLPPP

3

OLPOLP

0

An là người thắng cuộc trong cuộc thi "Tìm hiểu Đoàn Thanh niên Cộng sản Hồ Chí Minh" và được nhận phần thưởng của Ban tổ chức. Ban tổ chức chuẩn bị một bảng kích thước \(m \times n\). Các dòng của bảng được đánh số từ \(1\) đến \(m\), từ trên xuống dưới, dòng \(i\) (\(1 \le i \le m\)) có trọng số là \(a_i\). Các cột của bảng được đánh số từ \(1\) đến \(n\), từ trái qua phải, cột \(j\) (\(1 \le j \le n\)) có trọng số là \(b_j\). Ô nằm trên giao của dòng \(i\) và cột \(j\) được gọi là ô (\(i,j\)) và trên ô đó ghi một số nguyên có giá trị \(a_i + b_j\) (\(1 \le i \le m, 1 \le j \le n\)).

Để nhận phần thưởng, An được phép chọn một bảng có kích thước \(w \times h\) chiếm trọn \(w \times h\) ô của bảng và phần thưởng mà An nhận được sẽ có giá trị bằng tổng giá trị các ô nằm trong bảng con đó.

Yêu cầu: Hãy xác định tổng giá trị lớn nhất mà An có thể nhận được.

Input

• Dòng thứ nhất chứa bốn số nguyên dương \(m,n,w,h\) (\(w \le m, h \le n\)).
• Dòng thứ hai chứa \(m\) số nguyên \(a_1,a_2,...,a_m\) (\(|a_i| \le 10^6, i = 1,2,...,m\)).
• Dòng thứ ba chứa \(n\) số nguyên \(b_1,b_2,...,b_n\) (\(|b_j| \le 10^6, j = 1,2,...,n\)).

Output

• Một số nguyên duy nhất là tổng giá tri lớn nhất mà An có thể nhận được.

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(m,n \le 10, w = h = 1\).
• Subtask \(2\) (\(30\%\) số điểm): \(m,n \le 10\).
• Subtask \(3\) (\(20\%\) số điểm): \(m,n \le 10^3\).
• Subtask \(4\) (\(30\%\) số điểm): \(m,n \le 10^5\).

Example

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

6

Dựa trên ý tưởng của búp bê Nga Matrioska, công ty bánh Trung Thu có sản xuất những hộp bánh đặc biệt như sau: Trong một hộp bánh có thể chứa những hộp bánh nhỏ hơn, hộp bánh nhỏ nhất sẽ chứa bánh trung thu. Giả sử bánh trung thu là hộp bánh cấp \(0\) (bánh trung thu), hộp bánh cấp \(i\) (\(i \geq 1\)) sẽ chứa \(a_i\) hộp bánh cấp \(i-1\). Thấy ý tưởng rất độc đáo nên Bờm cũng đa mua một hộp bánh cấp \(N\) về để mở tiệc trung thu cho các bạn nhỏ.

Bờm muốn biết số lần mở hộp ít nhất để lấy được \(X\) chiếc bánh trung thu. Vì Bờm vẫn chưa biết có bao nhiêu bạn nhỏ tham gia tiệc trung thu nên để không tốn thời gian tính toán, Bờm sẽ chuẩn bị trước nhiều phương án.

Yêu cầu: Cho \(M\) phương án, với phương án thứ \(j\) (\(1 \le j \le M\)) cần \(X_j\) bánh trung thu, bạn hãy giúp Bờm tính xem cần ít nhất bao nhiêu lần mở hộp?

Input

• Dòng đầu tiên chứa hai số nguyên \(N\) và \(M\) (\(1 \le N,M \le 3 \times 10^5\)) là cấp của hộp bánh của Bờm và số phương án cần tính toán.
• Dòng thứ hai chứa \(N\) số nguyên \(a_i\) (\(1 \le a_i \le 10^9, 1 \le i \le N\)) mô tả hộp bánh cấp \(i\) sẽ chứa \(a_i\) hộp bánh cấp \(i-1\).
• Dòng thứ ba chứa \(M\) số nguyên \(X_j\) (\(1 \le X_j \le 10^{12}, 1 \le j \le M\)) tương ứng với số bánh trung thu cần lấy ra trong mỗi phương án.

Output

• Gồm $M dòng, dòng thứ \(j\) in ra số lần mở hộp ít nhất để lấy được \(X_j\) bánh trung thu.

Scoring

• Subtask \(1\) (\(60\%\) số điểm): \(N,M \le 1000\).
• Subtask \(2\) (\(40\%\) số điểm): không có ràng buộc gì thêm.

Example

3 3
3 3 3
2 8 13

3
5
8