JOI 2021 - Financial Report

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Dạng bài
Ngôn ngữ cho phép
Assembly, Awk, C, C#, C++, Clang, Cobol, D, Groovy, Haskell, JS, Java, Kotlin, Lua, Node JS, OCaml, ObjectiveC, PHP, Pascal, Perl, Prolog, Pypy, Pypy 3, Python, Ruby, Rust, Scala, Scratch, Swift
Điểm: 2500 (p) Thời gian: 3.0s Bộ nhớ: 512M Input: bàn phím Output: màn hình

JOI mart là một cửa hàng đã hoạt động được \(N\) ngày. Doanh thu vào ngày thứ \(i\) (\(1 \le i \le N\)) kể từ khi khai trương là \(A_i\) yen.

Bitaro, quản lý của JOI mart, chuẩn bị thuyết trình báo cáo tài chính. Anh sẽ chọn một số ngày và trình bày biểu đồ cột thể hiện doanh thu của những ngày đó theo thứ tự thời gian, rồi giải thích doanh thu đã thay đổi như thế nào. Để bài thuyết trình gây ấn tượng hơn, anh muốn chọn dữ liệu sao cho biểu đồ tạo được ấn tượng tốt nhất.

Giả sử Bitaro chọn dữ liệu của \(m\) ngày (\(1 \le m \le N\)), là các ngày \(p_1,p_2,\ldots,p_m\) kể từ khi khai trương, với \(1 \le p_1<p_2<\cdots<p_m \le N\). Điểm ấn tượng của biểu đồ được tính như sau:

Điểm ấn tượng là số lần doanh thu lập kỷ lục mới khi chỉ xét những ngày được chọn. Nói cách khác, đó là số chỉ số \(j\) (\(1 \le j \le m\)) thỏa mãn \(j=1\) hoặc

\[ \max\{A_{p_1},A_{p_2},\ldots,A_{p_{j-1}}\}<A_{p_j}. \]

Bitaro muốn tối đa hóa điểm ấn tượng, nhưng một số cách chọn dữ liệu có thể khiến bài thuyết trình trông thiếu tự nhiên. Vì vậy, anh quyết định chọn dữ liệu thỏa mãn đồng thời hai điều kiện sau:

  • Phải trình bày doanh thu mới nhất, tức là \(p_m=N\).
  • Hai ngày được chọn liên tiếp cách nhau không quá \(D\) ngày. Cụ thể, nếu \(m \ge 2\) thì \(p_{j+1}-p_j \le D\) với mọi \(j\) (\(1 \le j \le m-1\)).

Cho dữ liệu doanh thu của JOI mart kể từ khi khai trương và số nguyên \(D\), hãy tính điểm ấn tượng lớn nhất của biểu đồ mà Bitaro có thể trình bày.

Dữ liệu vào

Đọc dữ liệu từ đầu vào chuẩn theo định dạng sau. Mọi giá trị trong dữ liệu vào đều là số nguyên.

N D
A_1 ... A_N

Dữ liệu ra

Ghi một dòng chứa điểm ấn tượng lớn nhất của biểu đồ ra đầu ra chuẩn.

Ràng buộc

  • \(1 \le N \le 300\,000\).
  • \(1 \le D \le N\).
  • \(0 \le A_i \le 1\,000\,000\,000\) (\(1 \le i \le N\)).

Phân nhóm

  1. (14 điểm) \(N \le 20\).
  2. (14 điểm) \(N \le 400\).
  3. (20 điểm) \(N \le 7\,000\).
  4. (12 điểm) \(D=1\).
  5. (5 điểm) \(D=N\).
  6. (35 điểm) Không có giới hạn bổ sung.

Ví dụ

Ví dụ 1

Input 
7 1
100 600 600 200 300 500 500
Output 
3
Giải thích

Có bảy cách chọn biểu đồ thỏa mãn các điều kiện của đề bài:

  • Chọn các ngày \(1,2,3,4,5,6,7\): điểm ấn tượng là \(2\).
  • Chọn các ngày \(2,3,4,5,6,7\): điểm ấn tượng là \(1\).
  • Chọn các ngày \(3,4,5,6,7\): điểm ấn tượng là \(1\).
  • Chọn các ngày \(4,5,6,7\): điểm ấn tượng là \(3\).
  • Chọn các ngày \(5,6,7\): điểm ấn tượng là \(2\).
  • Chọn các ngày \(6,7\): điểm ấn tượng là \(1\).
  • Chọn ngày \(7\): điểm ấn tượng là \(1\).

Vì vậy, điểm ấn tượng lớn nhất là \(3\); chương trình cần ghi 3.

Ví dụ này thỏa mãn các giới hạn của phân nhóm 1, 2, 3, 4 và 6.

Ví dụ 2

Input 
6 6
100 500 200 400 600 300
Output 
4
Giải thích

Điểm ấn tượng lớn nhất đạt được khi Bitaro chọn các ngày \(1,3,4,5,6\). Các doanh thu được chọn lần lượt là \(100,200,400,600,300\) yen. Do có bốn lần lập kỷ lục doanh thu mới trong dữ liệu được chọn, điểm ấn tượng là \(4\). Vì vậy, ghi 4.

Ví dụ này thỏa mãn các giới hạn của phân nhóm 1, 2, 3, 5 và 6.

Ví dụ 3

Input 
11 2
1 4 4 2 2 4 9 5 7 0 3
Output 
4
Giải thích

Chẳng hạn, điểm ấn tượng lớn nhất đạt được khi chọn các ngày \(1,3,5,6,8,9,11\). Các doanh thu được chọn lần lượt là \(1,4,2,4,5,7,3\) yen. Do có bốn lần lập kỷ lục doanh thu mới trong dữ liệu được chọn, điểm ấn tượng là \(4\). Vì vậy, ghi 4.

Có nhiều cách chọn dữ liệu khác cũng thỏa mãn các điều kiện của đề bài và đạt điểm ấn tượng \(4\).

Ví dụ này thỏa mãn các giới hạn của phân nhóm 1, 2, 3 và 6.

Nguồn

JOI Open Contest 2021, JCIOI. Bản dịch tiếng Việt từ đề chính thức; phát hành theo giấy phép CC BY-SA 4.0.

Tệp

Bình luận

Mới nhất
Tải bình luận...

Không có bình luận nào.

Kỳ thi: