Bỏ qua đến nội dung

MAXSUM

Mã bài: prefix01 Nhóm: Uncategorized Dạng bài: Undefined

Giới hạn thời gian
1,0 s
Giới hạn bộ nhớ
256 MB
Điểm
100
Tỉ lệ AC
10,8%
Người giải
3

Cho một mảng gồm n số nguyên, nhiệm vụ của bạn là tìm tổng lớn nhất của một mảng con liên tiếp có độ dài trong khoảng từ a đến b.

Input

  • Dòng đầu tiên chứa ba số nguyên n, a và b (1 \le n \le 5.10^6, 1 \le a \le b \le n) lần lượt là số phần tử của mảng, độ dài nhỏ nhất và độ dài lớn nhất của mảng con.
  • Dòng thứ hai chứa n số nguyên x_1,x_2,...,x_n (|x_i| \le 10^9) là các giá trị của mảng.

Output

  • In ra một số nguyên duy nhất là tổng lớn nhất của một mảng con.

Samples

Sample Input 1
8 1 2
-1 3 -2 5 3 -5 2 2
Sample Output 1
8

Scoring

  • Subtask 1 - 14 điểm: n \le 100
  • Subtask 2 - 10 điểm: n \le 5000
  • Subtask 3 - 12 điểm: 0 \le x_i \le 1
  • Subtask 4 - 10 điểm: x_i \le 0
  • Subtask 5 - 16 điểm: a=1, b=n
  • Subtask 6 - 22 điểm: n \le 2.10^5
  • Subtask 7 - 16 điểm: Không còn ràng buộc gì thêm

Bình luận