Bài tập

Trong một vương quốc xa xưa, có một khu rừng ma thuật được chia thành \(n \times n\) ô vuông, mỗi ô vuông có thể chứa đá quý (\(1\)) hoặc trống rỗng (\(0\)). Nhiệm vụ của các pháp sư trong vương quốc là đếm số lượng hình chữ nhật con, với các cạnh song song với cạnh của khu rừng, chỉ chứa các ô rỗng (các ô vuông chứa \(0\)).

Để làm cho nhiệm vụ thêm phần thú vị, các pháp sư được yêu cầu cập nhật các thay đổi trạng thái của một ô vuông từ rỗng (\(0\)) thành chứa đá quý (\(1\)) hoặc ngược lại. Sau mỗi thay đổi, họ lại phải đếm lại số lượng hình chữ nhật con thỏa mãn yêu cầu.

Nhận thấy đây là một bài toán quá hóc búa, các pháp sư chỉ còn có thể trông cậy vào bạn.
Lưu ý: các cập nhật sẽ thật sự thay đổi giá trị của một ô và có ảnh hưởng về sau.

Input

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(q\) \((1 \leq n, q \leq 5000)\), lần lượt là kích thước bảng và số lượng truy vấn.
• \(n\) dòng tiếp theo, mỗi dòng chứa một chuỗi ký tự \(0\) và \(1\) độ dài \(n\), mô tả trạng thái ban đầu của khu rừng.
• \(q\) dòng cuối, mỗi dòng chứa hai số nguyên \(r\) và \(c\) \((1 \leq r, c \leq n)\), mô tả tọa độ của ô vuông thay đổi trạng thái trong truy vấn thứ \(i\).

Output

In ra \(q + 1\) dòng:

• Dòng đầu tiên là số lượng hình chữ nhật con chỉ chứa các ô trống rỗng (\(0\)) trong trạng thái ban đầu của khu rừng.
• Mỗi dòng trong \(q\) dòng tiếp theo ghi số lượng hình chữ nhật thỏa mãn yêu cầu sau mỗi lần thay đổi trạng thái của ô vuông.

Example

4 3
0001
0100
1000
0010
2 3
2 2
3 1

29
23
31
45

Scoring

• Có \(20\%\) số test ứng với \(n, q \leq 50\).
• Có \(20\%\) số test khác ứng với \(n, q \leq 150\).
• Có \(20\%\) số test khác ứng với \(n, q \leq 400\).
• Có \(20\%\) số test khác ứng với \(n, q \leq 1000\).
• Có \(20\%\) số test khác ứng với \(n, q \leq 5000\).

Sau cuộc phiêu lưu cùng nhau, Dế Mèn và Dế Trũi lên kế hoạch trở về quê nhà. Hành trình trở về quê của hai bạn sẽ đi qua \(N\) thành phố, các thành phố lần lượt được đánh số từ \(1\) đến \(N\). Giá bán một xe cỏ tại thành phố thứ \(i\) (\(1 \le i \le N\)) là \(A_i\) (\(1 \le A_i \le 10^9\)). Nếu mua một xe cỏ ở thành phố \(i\) và mang đến bán ở thành phố \(j\) thì thu được lợi nhuận là \(A_j - A_i\) (\(1 \le i < j \le N\)).

Vì giao thông không thuận lợi nên trên đường đi hai bạn chỉ mang theo được tối đa một xe cỏ. Để đảm bảo thời gian di chuyển nên số lần mua và bán một xe cỏ không được vượt quá \(K\) lần.

Yêu cầu:
Hãy lập trình tính tổng lợi nhuận tối đa mà hai bạn có thể thu được trên hành trình trở về quê nhà.

Input

• Dòng đầu ghi hai số nguyên dương lần lượt \(N, K\) (\(K \le N \le 200000\)).
• Dòng thứ hai ghi lần lượt \(N\) số nguyên dương \(A_1, A_2, \ldots, A_N\).
• Các số trong tệp cách nhau ít nhất một dấu cách.

Output

• Ghi ra một số nguyên duy nhất là tổng lợi nhuận tối đa có thể thu được.

Example

5 1
4 1 3 5 6

5

5 2
1 4 2 5 6

7

Scoring

• Có 20% số điểm tương ứng với \(K = 1\);
• Có 30% số điểm tương ứng với \(K = 2\);
• Có 30% số điểm tương ứng với \(3 \le K \le 100\);
• Có 20% số điểm tương ứng với \(100 < K, N \le 200000\).

Sau khi hoàn thành bài thi, Alice, Bob cùng các bạn thi lập trình tham quan trại nghiên tại công viên ánh sáng. Công viên có một dàn đèn gồm \(n\) bóng đèn được đặt vị trí theo phương ngang. Các đèn đánh số thứ tự từ \(1\) đến \(n\) theo hướng từ trái sang phải. Mỗi bóng đèn có ánh sáng xanh hoặc màu đỏ.

Nhìn vào dàn đèn với ánh sáng màu xanh, màu đỏ rực rỡ, Alice đã yêu cầu Bob trả lời câu hỏi:

Nếu phải chọn \(k\) bóng đèn kề nhau và đổi trạng thái màu của các bóng đèn đó (màu xanh chuyển sang màu đỏ, màu đỏ chuyển sang màu xanh) thì số lượng bóng đèn màu xanh trên dàn đèn nhiều nhất là bao nhiêu?

Input

Dữ liệu: Cho từ tệp vào DANDEN.INP gồm:

• Dòng thứ nhất ghi hai số nguyên dương \(n, k\) (\(3 \le n \le 10^6; 1 \le k \le n\)).
• Dòng thứ hai ghi \(n\) số nguyên \(a_1, a_2, \ldots, a_n\) (\(0\) biểu thị đèn màu đỏ, \(1\) biểu thị đèn màu xanh).

Output

Kết quả: Ghi ra tệp DANDEN.OUT gồm một số nguyên là số bóng đèn màu xanh lớn nhất có thể đạt được.

Example

8 2
1 1 0 0 0 1 1 0

6

8 2
1 1 1 1 1 1 1 1

8

8 2
1 0 1 0 1 0 1 1

5

Scoring

Giới hạn:

• 40% test ứng với \(k = 1\).
• 40% test ứng với \(k = 2\).
• 20% test còn lại không giới hạn gì thêm.

Cho một dãy \(A\) gồm \(n\) số nguyên dương \(A_1\), \(A_2\), \(A_3\), ..., \(A_n\). Có bao nhiêu cặp chỉ số \((i,j)\) thỏa mãn \(1 \leq i < j \leq n\) để tổng \(A_i+A_j\) chia hết cho \(3\).

Input

Dữ liệu vào: Đọc từ tệp dayso.inp gồm \(2\) dòng:

• Dòng đầu tiên chứa số nguyên \(n\) \((2 \leq n \leq 10^5)\).
• Dòng thứ \(2\) chứa \(n\) số nguyên dương \(A_1, A_2, A_3, ..., A_n\), mỗi số không vượt quá \(10^9\), giữa hai số cách nhau \(1\) dấu cách.

Output

Dữ liệu ra: Ghi ra tệp dayso.out một dòng duy nhất là số cặp tìm được.

Example

7
3 1 2 9 5 3 5

6

Scoring

• \(70\%\) số điểm có \(n \leq 10^4\).
• \(30\%\) số điểm còn lại không có ràng buộc gì thêm.