Lướt sóng

Xem PDF
Tác giả:
letangphuquy
Dạng bài
Điểm: 1600 (p) Thời gian: 2.0s Bộ nhớ: 512M Input: bàn phím Output: màn hình

Trải qua quá nhiều năm thăng trầm trong đầu tư chứng khoán, Nam đã trở thành một bậc thầy đầu tư. Hơn cả thế, Nam còn có năng lực dự đoán tương lai và biết trước được giá cổ phiếu IVN sẽ lên xuống \(n\) lần trong hôm nay. Cụ thể, Nam biết trước nếu "vào lệnh" vào đợt thứ \(i\) thì sẽ đem lại lợi nhuận là \(a_i\) VNĐ. Nếu \(a_i\) âm nghĩa là Nam sẽ thua lỗ \(-a_i\) VNĐ khi vào lệnh ở đợt \(i\).
Tuy nhiên, vì đã quá giàu nên Nam không muốn tổng lợi nhuận là lớn nhất. Thay vào đó, Nam muốn độ "chất chơi" phải cao, tức là đặt lệnh vào càng nhiều đợt càng tốt, kể cả có những đợt âm rất nhiều tiền (và dù Nam đã biết trước điều đó!). Để không bị đánh giá là đầu tư thiếu thông minh, Nam muốn đảm bảo sau mỗi lần vào lệnh, tổng lợi nhuận thu được là không âm.
Là một trợ lý mới được tuyển dụng, bạn được Nam nhờ tính độ "chất chơi".

Input

  • Dòng đầu tiên chứa \(n\) \((1 \le n \le 2.10^5)\): số đợt thay đổi của cổ phiếu
  • Dòng tiếp theo chứa \(n\) số nguyên \(a_1, a_2, a_3, \dots, a_n (-10^9 \le a_i \le 10^9)\): nếu Nam vào lệnh ở đợt thứ \(i\) thì tổng lợi nhuận tăng lên \(a_i\).

Output

  • Dòng duy nhất chứa số lần vào lệnh nhiều nhất có thể, thỏa mãn yêu cầu trên.

Scoring

  • Subtask 1 (\(40\%\) số điểm): \(1 \le n \le 20\)
  • Subtask 2 (\(40\%\) số điểm): \(1 \le n \le 1000\)
  • Subtask 3 (\(20\%\) số điểm): Không có giới hạn thêm.

Sample

Input 
6
4 -4 1 -3 1 -3
Output 
5
Note

Nam chỉ cần bỏ qua đợt thứ \(2\). Khi đó, tổng lợi nhuận thu được khi lần lượt vào lệnh ở các đợt \(1,3,4,5,6\) là:

  • \(0 + 4 = 4\)
  • \(4 + 1 = 5\)
  • \(5 + (-3) = 2\)
  • \(2 + 1 = 3\)
  • \(3 + (-3) = 0\)
    Vì không có lúc nào mà tổng này âm nên cách làm thỏa mãn yêu cầu

Bình luận