Bài tập

BigZero có một bể cá. Mỗi ngày đàn cá ăn hết đúng 3 gói thức ăn. Biết trước giá bán trong \(n\) ngày lần lượt là \(a_1, a_2, \dots, a_n\), mỗi ngày được mua nhiều gói với giá bán của ngày đó, thức ăn thừa có thể được dùng cho các ngày tiếp theo.

Yêu cầu: Cho số nguyên dương \(n\) và các số nguyên dương \(a_1, a_2, \dots, a_n\), trong đó \(a_i\) là giá bán một gói thức ăn trong ngày thứ \(i\) \((1 \le i \le n \le 10^6; a_i \le 10^9)\). Hãy xác định số tiền tối thiểu để mua thức ăn cho đàn cá trong \(n\) ngày.

Input

Vào từ tệp văn bản FISH.INP:

• Dòng thứ nhất chứa một số nguyên dương \(n\) \((1 \le n \le 10^6)\).
• Dòng thứ hai chứa \(n\) số nguyên dương \(a_1, a_2, \dots, a_n\) \((1 \le i \le n; a_i \le 10^9)\).

Output

Ghi ra tệp văn bản FISH.OUT một số nguyên duy nhất là số tiền tối thiểu để mua thức ăn cho đàn cá trong \(n\) ngày.

Example

3
2 3 5

18

3
5 3 2

30

3
5 2 3

27

Scoring

• Có \(30\%\) số test ứng với \(30\%\) số điểm của bài thỏa mãn: \(a_1 \le a_2 \le \dots \le a_n\).
• Có \(30\%\) số test khác ứng với \(30\%\) số điểm của bài thỏa mãn: \(a_1 \ge a_2 \ge \dots \ge a_n\).
• \(40\%\) số test còn lại ứng với \(40\%\) số điểm của bài không có ràng buộc gì thêm.

Cho một dãy \(n\) số nguyên \(a_1, a_2, \ldots, a_n\), cùng với hai số nguyên \(k\) và \(g\). Nhiệm vụ của bạn là đếm số cách chọn một tập hợp con gồm đúng \(k\) số từ dãy \(a\) sao cho ước chung lớn nhất (UCLN) của các số trong tập hợp đó bằng đúng \(g\).

Cụ thể hơn, bạn cần tìm số lượng các tập chỉ số \(1 \le i_1 < i_2 < \ldots < i_k \le n\) sao cho \(\gcd(a_{i_1}, a_{i_2}, \ldots, a_{i_k}) = g\).

Input

• Dòng đầu tiên chứa ba số nguyên \(n, k\) và \(g\) (\(1 \le k \le n \le 10^6\), \(1 \le g \le 10^6\)).
• Dòng tiếp theo chứa \(n\) số nguyên \(a_1, a_2, \ldots, a_n\) (\(1 \le a_i \le 10^6\)).

Output

• In ra một số nguyên duy nhất là đáp án của bài toán, sau khi chia lấy dư cho \(10^9 + 7\).

Example

6 2 2
1 2 3 4 5 6

3

Đất nước Z gồm có \(n\) thành phố và \(n - 1\) con đường hai chiều giữa các thành phố. Hệ thống đường đảm bảo từ thành phố bất kỳ có thể đi đến được thành phố bất kỳ khác. Do nhu cầu xây dựng phát triển hạ tầng trong thời gian tới tăng cao, Bộ Giao thông đã thu thập, đánh giá có \(m\) dự án cần vận chuyển giữa các cặp thành phố, cụ thể dự án thứ \(k\ (1 \le k \le m)\) cho biết nhu cầu đi lại giữa hai thành phố \(i_k\) và \(j_k\) là \(w_k\).

Bộ Giao thông dự định sẽ nâng cấp một tuyến đường được mô tả bằng hai thành phố \(u, v\), khi đó toàn bộ các con đường nằm trên tuyến đường đi lại giữa hai thành phố \(u, v\) đều sẽ được nâng cấp. Hiệu quả việc nâng cấp tuyến đường giữa hai thành phố
\(u, v\) được tính bằng tổng các \(w_k\) nếu \(i_k, j_k\) thuộc trên đường đi lại giữa \(u, v\ (1 \le k \le m)\).

Yêu cầu: Tìm tuyến đường để nâng cấp có hiệu quả là lớn nhất.

Input

• Dòng đầu chứa số nguyên dương \(n\).
• Tiếp theo là \(n- 1\) dòng, mỗi dòng chứa hai số mô tả \(n-1\) con đường.
• Dòng tiếp theo chứa số nguyên dương \(m\).
• Tiếp theo là \(m\) dòng, dòng thứ \(k\) chứa ba số nguyên dương \(i_k, j_k, w_k\ (1 \le i_k, j_k \le n; w_k \le 1000)\).

Output

• Gồm một số nguyên là hiệu quả nâng cấp lớn nhất tìm được.

Example

5
1 2
1 3
2 4
2 5
4
2 3 10
1 5 10
1 4 5
1 2 5

25

Scoring

• Có \(20\%\) số test ứng với \(20\%\) số điểm của bài có \(n \le 100; m \le 100\).
• Có \(20\%\) số test khác ứng với \(20\%\) số điểm của bài có \(n \le 100; m \le 10^5\).
• Có \(30\%\) số test khác ứng với \(30\%\) số điểm của bài có \(n \le 1000; m \le 10^5\).
• Có \(20\%\) số test khác ứng với \(20\%\) số điểm của bài có \(n \le 20000; m \le 10^5\).
• Có \(10\%\) số test còn lại ứng với \(10\%\) số điểm của bài có \(n,m \le 2 \times 10^5\).

Cho một bảng hình chữ nhật kích thước \(m \times n\) được chia thành lưới ô vuông đơn vị gồm \(m\) hàng và \(n\) cột. Các hàng được đánh số từ \(1\) đến \(m\) theo thứ tự từ trên xuống dưới, các cột được đánh số từ \(1\) đến \(n\) theo thứ tự từ trái sang phải.

Người ta tô màu các ô của bảng theo từng cột như sau: Trên mỗi cột \(j\), \(h_j\) ô đầu tiên từ trên xuống được tô màu vàng, \(m - h_j\) ô còn lại được tô màu đen. Như vậy, bảng màu được xác định hoàn toàn bởi \(m\), \(n\) và dãy \(h_1, h_2, \dots, h_n\).

\begincenter

\endcenter

Input

• Dòng đầu tiên chứa hai số nguyên dương \(m, n\) (\(m, n \le 5 \times 10^5\)).
• Dòng thứ hai chứa \(n\) số nguyên \(h_1, h_2, \dots, h_n\) (\(0 \le h_j \le m\)).

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 một số nguyên duy nhất là diện tích lớn nhất của hình chữ nhật có các cạnh song song với cạnh bảng và có tất cả các ô cùng màu (toàn vàng hoặc toàn đen).

Example

5 9
1 3 4 4 5 4 4 3 1

21

Scoring

• Subtask 1 (\(30\%\) số điểm): \(m, n \le 400\).
• Subtask 2 (\(30\%\) số điểm): \(m, n \le 10^4\).
• Subtask 3 (\(40\%\) số điểm): \(m, n \le 5 \times 10^5\).