Cho ma trận A các số nguyên có N hàng và M cột. Tim đường đi từ ở [1, 1] tới Ô [N, M] sao cho tổng các số trên đường đi là lớn nhất có thể, biết rằng ở mỗi bước chi có thể đi từ ô hiện tại xuống ô phía dưới hoặc đi sang phải.

Đầu vào: Dòng đầu tiên N và M; N dòng tiếp theo mỗi dòng gồm M phần tử.

Ràng buộc: 1 <= N, M <= 100: 1 <= A[i][j] <= 10^9

Đầu ra: In ra đường đi có tổng lớn nhất.

Input:

3 3
1 2 2
3 10 2
5 7 2

Output:

23

Cho mảng 2 chiều A gồm N hàng và N cột, hãy tim 1 đường đi từ dòng 1 tới dòng N sao cho các phần tử trên đường đi đó là lớn nhất có thế. Biết rằng ở mỗi bước đi từ ô hiện tại chỉ có thế đi xuống ô dưới bên trái, ô dưới bên phải hoặc ô dưới của ô hiện tại. Hây tìm 1 đường đi có tổng các số trên đường đi là lớn nhất

Đầu vào:

Dòng 1 là N

N dòng tiếp theo mỗi dòng gồm N số

Ràng buộc: 1 <= N <= 100; 1 <= A(i][j] <= 100

Đầu ra: In ra kết quả của bài toán

Input:

5
5 1 8 6 7
6 0 0 3 7
3 4 1 5 3
9 6 9 2 2
5 3 4 5 3

Output:

33

Cho một số tự nhiên N được biểu diễn như một xâu kí tự, bạn hãy tính tổng của tất cả các số tạo bởi các xâu con liên tiếp của N, ví dụ N = 235 thì ta có tổng = 2 + 3 + 5 + 23 + 35 + 235.

Đầu vào: Dòng duy nhất chứa số nguyên dương N

Ràng buộc: 1 <= N <= 10^12

Đầu ra: In ra kết quả của bài toán

Input

1807

Output:

2915

Cho xâu S. Hãy tìm độ dài của xâu con đối xứng dài nhất trong S (Xâu con đối xứng là xâu con của S mà đọc xuôi hay ngược đều giống nhau, ở đây xét xâu con không cần liên tiếp - Subsequence).

Dữ liệu vào:

Xâu S.

Dữ liệu ra:

Độ dài lớn nhất.

Ràng buộc:

Độ dài S <= 1000

Ví dụ:

Input:

BBABCBCAB

Output:

7

Giải thích: BABCBAB

Một dãy số được gọi là Bitonic nếu nó tăng dần rồi sau đó giảm dần. Cho dãy số A gồm N phần tử, hãy tìm độ dài của dãy con Bitonic dài nhất của A.

Dữ liệu vào:

Dòng 1: Số nguyên N (1 <= N <= 2000).

Dòng 2: N số nguyên A[i].

Dữ liệu ra:

Độ dài dãy con Bitonic dài nhất.

Ví dụ:

Input:

8 
1 11 2 10 4 5 2 1

Output:

6

Cho dãy số A gồm N số nguyên. Với mỗi đoạn con liên tiếp A[i...j], ta tính tổng các phần tử của nó. Hãy tính tổng của tất cả các tổng đoạn con đó. (Lưu ý: Bài này có thể giải bằng toán học thuần túy hoặc quy hoạch động đơn giản).

Dữ liệu vào:

Dòng 1: Số nguyên N (1 <= N <= 10^5).

Dòng 2: N số nguyên A[i] (|A[i]| <= 10^9).

Dữ liệu ra:

Tổng của tất cả các đoạn con modulo 10^9 + 7.

Ví dụ:

Input:

3 
1 2 3

Output:

20