Bài 4. Dãy con tăng (HSG THPT Bắc Ninh 2026)

Xem dạng PDF

Gửi bài giải

Điểm: 1,00 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 256M
Input: stdin
Output: stdout

Tác giả:
Nguồn bài:
HSG THPT Bắc Ninh 2026
Dạng bài
Ngôn ngữ cho phép
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Tom rất yêu thích việc liệt kê các dãy con (đặc biệt là các dãy con tăng) của một dãy số nguyên. Ta gọi ~A'~ là một dãy con tăng của dãy ~A~ nếu ~A'~ thu được bằng cách bỏ đi một số phần tử của ~A~, giữ nguyên thứ tự các phần tử còn lại và các phần tử trong ~A'~ được sắp xếp theo thứ tự tăng nghiêm ngặt.

Ví dụ: Cho dãy ~A = [6, 1, 9, 5, 8, 5]~. Các dãy [1, 5, 8] và [1, 8] là dãy con tăng của ~A~ nhưng [1, 5, 5] và [6, 1, 5] thì không phải.

Với niềm đam mê tìm hiểu các con số, Tom định nghĩa độ khó của một số nguyên là tích các chữ số của nó.

Ví dụ: Hai số 1234 và 813 đều có độ khó bằng 24, còn số 8 có độ khó bằng chính nó.

Tom viết ra một dãy số ~A~ nguyên ngẫu nhiên, không có phần tử âm và đố Been tìm ra độ khó lớn nhất của dãy con tăng nghiêm ngặt trong dãy ~A~. Biết rằng độ khó của một dãy số được quy ước là tổng độ khó của tất cả các phần tử trong dãy đó.

Yêu cầu: Cho dãy ~A~ gồm ~N~ số nguyên không âm ~A_1, A_2, \ldots, A_N~. Tìm độ khó lớn nhất của dãy con tăng trong dãy ~A~.

Dữ liệu vào

Dữ liệu vào từ thiết bị vào chuẩn gồm hai dòng:

  • Dòng 1: Ghi số nguyên dương ~N (1 \le N \le 2 \times 10^5)~;
  • Dòng 2: Ghi ~N~ số nguyên không âm ~A_1, A_2, A_3, \ldots, A_N (0 \le A_i \le 10^9; i = 1, 2, \ldots, N)~.

Kết quả

Ghi ra thiết bị ra chuẩn một số nguyên là kết quả cần tìm.

Ví dụ

Input 1

5
5 101 54 123 56

Output 1

55

Giải thích:
Dãy [5, 54, 56] có độ khó lớn nhất trong số các dãy con tăng. Độ khó của nó là ~5 + 20 + 30 = 55~

Ràng buộc

  • Subtask 1: Có 20% số test ứng với 20% số điểm có ~N \le 20~;
  • Subtask 2: Có 20% số test ứng với 20% số điểm có ~N \le 2000~;
  • Subtask 3: Có 60% số test ứng với 60% số điểm có ~N \le 2 \times 10^5~.

Chương trình đọc dữ liệu từ bàn phím (stdin) và ghi kết quả ra màn hình (stdout). Vẫn có thể giữ đoạn freopen("DAYCON.INP", ...) nếu đặt trong điều kiện if (fopen("DAYCON.INP", "r")).


Đang tải...