Tài là học sinh giỏi toán và ham mê học hỏi. Tài rất thích thú với những cặp số đặc biệt. Cặp số đặc biệt là những cặp số có tổng chia hết cho 3.

Cho một dãy a[] gồm N số nguyên dương. Tài muốn biết trong dãy a[], có bao nhiêu cặp chỉ số (i, j) với (1 ≤ i < j ≤ n) sao cho tổng a[i] và a[j] chia hết cho 3.

Yêu cầu: Bạn hãy giúp bạn Tài đếm xem có bao nhiêu cặp số này nhé.

Đầu vào

• Dòng đầu tiên là N : số phần tử trong dãy số

• Dòng thứ 2 là N số trong dãy a[]

Giới hạn

• 1≤N≤10^6

• 1≤a[i]≤10^6

• 60% số điểm tương ứng với test có 1 < N ≤ 10^3.

• 40% số điểm tương ứng với test khác có 10^3 < N ≤ 10^6.

Đầu ra

• Một số nguyên duy nhất là số lượng cặp số của dãy a có tổng chia hết cho 3.

Ví dụ :

Input 01

7
3 6 8 5 3 5 7

Output 01

6

Giải thích :

6 cặp số tìm được có chỉ số là: (1,2), (1,5), (2,5), (3,7), (4,7), (6,7)

Nhân dịp chào mừng ngày thành lập Đoàn TNCS Hồ Chí Minh, Đoàn trường tổ chức vẽ một bức tranh không lồ trên tường rào. Bức tường được chia sẵn thành n phần liên tiếp nhau. Do độ khó khác nhau, phần tường thứ i cần thời gian là a[i] phút để vẽ xong. Có K nhóm học sinh câu lạc bộ mỹ thuật được giao nhiệm vụ hoàn thiện bức tranh này.

Để hoàn thành bức tranh, thầy Bí thư Đoàn trường quyết định chia n phần tường này thành đúng K đoạn liên tiếp nhau (mỗi nhóm phụ trách vẽ một đoạn, mỗi đoạn có thể gồm nhiều phần liên tiếp). Thời gian vẽ xong một đoạn là tổng thời gian vẽ các phần trong đoạn đó. Thời gian để hoàn thành bức tranh bằng thời gian vẽ của đoạn lâu nhất trong một cách chia.

Yêu cầu: Bạn hãy giúp thầy Bí thư Đoàn trường tìm thời gian hoàn thành bức tranh nhanh nhất.

Ví dụ: Cho bức tường có n = 4, thời gian lần lượt vẽ các phần là: 1, 2, 3 và 4 phút. Với K = 3 thì có các cách chia như sau:

Cách 1: (1), (2), (3, 4): Thời gian hoàn thành bức tranh là 7 phút;

Cách 2: (1), (2, 3), (4): Thời gian hoàn thành bức tranh là 5 phút;

Cách 3: (1, 2), (3), (4): Thời gian hoàn thành bức tranh là 4 phút.

Đầu vào

• Dòng 1: Chứa hai số nguyên dương n và K.

• Dòng 2: Chứa n số nguyên dương a₁, a₂, ..., aₙ (aᵢ ≤ 10⁹). Các số cách nhau ít nhất một dấu cách.

Giới hạn

• 30% số điểm tương ứng số test có n ≤ 10³ và K = 2.

• 40% số điểm tương ứng số test khác có n ≤ 10³ và K = 3.

• 30% số điểm tương ứng số test khác có n ≤ 10⁵ và K ≤ n.

Đầu ra

• Một số nguyên duy nhất thoả mãn yêu cầu của đề toán.

Ví dụ :

Input 01

4 3
1 2 3 4

Output 01

4

Cho hình chữ nhật kích thước m × n (m hàng, n cột) được chia thành lưới các ô vuông đơn vị. Các hàng được đánh số từ 1 đến m, từ trên xuống dưới, các cột được đánh số từ 1 đến n, từ trái qua phải. Ô nằm trên hàng i, cột j gọi là ô (i, j) và chứa giá trị aᵢ,ⱼ (1 ≤ aᵢ,ⱼ ≤ 10⁶, 1 ≤ i ≤ m, 1 ≤ j ≤ n). Gọi trọng số của một hình vuông con được tính bằng giá trị của số nhỏ nhất trong hình vuông con đó.

Yêu cầu : Với số nguyên dương k cho trước, hãy tìm trọng số lớn nhất trong số các hình vuông con kích thước k × k.

Gợi ý : Bài này có thể làm bằng tìm kiếm nhị phân kết quả gọi là X, gọi mảng b[][] trong đó b[i][j] = 1 nếu a[i][j] < X, bằng 0 nếu ngược lại, bây giờ tìm kiếm nhị phân từ 1 tới 10^6. Với mỗi giá trị bạn cần kiểm tra xem trong mảng 2 chiều b có mảng con cỡ k * k nào mà toàn là số 0 hay không? Việc kiểm tra nay có thể thực hiện được bằng cách xây dựng mảng cộng dồn của mảng b, sau đó truy vấn nhanh cách hình vuông cỡ k * k trên mảng cộng dồn này sẽ cho biết tổng tất cả các số trong hình vuông đó, nếu tổng các số trong hình vuông đó bằng 0 tức là toàn bộ các số trong mảng a[][] tại hình vuông tương ứng đó đều >= X. Mỗi lần check sẽ mất O(N^2), độ phức tạp toàn bộ của chương trình sẽ là O(N^2 * log10^6)

Đầu vào

• Dòng 1: Chứa ba số nguyên dương m, n, k (1 ≤ m, n ≤ 1000; k ≤ m, k ≤ n).

• m dòng tiếp theo, mỗi dòng chứa n số nguyên dương aᵢ,ⱼ thể hiện lưới hình chữ nhật. Các số trên cùng dòng cách nhau ít nhất một dấu cách.

Giới hạn

• 70% số điểm tương ứng số test có 1 ≤ m, n ≤ 100.

• 30% số điểm tương ứng số test khác có 100 < m, n ≤ 1000.

Đầu ra

• Một số nguyên duy nhất thoả mãn yêu cầu bài toán.

Ví dụ :

Input 01

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

Output 01

4

Giải thích

Đáp án thu được là 4, hình vuông thỏa mãn là hình vuông 
5 4 
5 6

Nhân dịp kỷ niệm 100 năm ngày thành lập công ty, để ghi nhận sự cống hiến của các thành viên, công ty tổ chức chương trình trao thưởng cho tất cả các nhân viên. Ban tổ chức chuẩn bị sẵn n hộp phần thưởng, mỗi hộp được đặt trên một bàn, các bàn đánh số từ 1 đến n. Trên hộp phần thưởng thứ i (i = 1...n) có dán nhãn là aᵢ và trong đó có phần thưởng trị giá wᵢ.

Nhân viên có thể chọn một hay nhiều hộp phần thưởng liên tiếp hay không liên tiếp từ hộp phần thưởng ở bàn 1 đến bàn n, hộp phần thưởng chọn sau phải có nhãn lớn hơn nhãn trên hộp phần thưởng chọn trước, tức là:

Yêu cầu: Bạn hãy giúp nhân viên chọn cho mình các hộp phần thưởng để có tổng trị giá là lớn nhất.

Đầu vào

• Dòng 1: Chứa số nguyên dương n (n ≤ 5.10⁵).

• n dòng tiếp theo, dòng thứ i (i = 1...n) chứa 2 số nguyên dương aᵢ (aᵢ ≤ 10⁹) và wᵢ (wᵢ ≤ 10⁶). Các số trên cùng dòng cách nhau ít nhất một dấu cách.

Giới hạn

• Có 60% số điểm tương ứng số test có n ≤ 10³.

• Có 40% số điểm tương ứng số test khác có 10³ < n ≤ 5.10⁵.

Đầu ra

• Một số nguyên duy nhất thoả mãn yêu cầu bài toán.

Ví dụ :

Input 01

4
1 5
1 3
5 6
5 7

Output 01

12

Giải thích

Chọn hộp phần thưởng thứ 1 và thứ 4 có tổng trị giá bằng 12