KẾ HOẠCH THI ĐẤU

Xem PDF

Điểm: 100 (p) Thời gian: 1.0s Bộ nhớ: 512M Input: bàn phím Output: màn hình

Nam là một vận động viên quần vợt chuyên nghiệp. Trong một hệ thống thi đấu quần vợt, người ta tổ chức \( n \) giải đấu đánh số từ 1 đến \( n \). Giải đấu thứ \( i \) được tổ chức vào ngày thứ \( a_i \) (ngày Ban tổ chức ra quyết định là ngày thứ 1) và mỗi vận động viên tham gia được cộng điểm thưởng là \( b_i \). Để đảm bảo sức khỏe, huấn luyện viên quyết định hai giải đấu mà Nam chọn tham dự phải cách xa nhau ít nhất là \( k \) ngày (\(|a_i - a_j| \geq k\) nếu Nam tham dự cả giải thứ \( i \) và giải thứ \( j \)).
Bạn hãy giúp Nam chọn lựa các giải thi đấu sao cho tổng số điểm thưởng là nhiều nhất.

Dữ liệu:

  • Dòng đầu tiên là hai số nguyên \( n \)\( k \) (\( 1 \leq n \leq 10^5, 1 \leq k \leq 100 \))
  • Dòng thứ hai chứa \( n \) số nguyên \( a_1, a_2, ..., a_n \) (\( 1 \leq a_i \leq 10^9 \)) là ngày thi đấu của các giải 1, 2, ..., \( n \). Dữ liệu cho đảm bảo \( a_1 < a_2 < a_3 < ... < a_n \).
  • Dòng thứ ba chứa \( n \) số nguyên \( b_1, b_2, \dots, b_n \) (\( 1 \leq b_i \leq 10^4 \)) là số điểm thưởng của các giải 1, 2, ..., \( n \).

Kết quả:

  • Một số nguyên duy nhất là tổng số điểm thưởng lớn nhất mà Nam có thể có được.

Ví dụ:

INPUT OUTPUT
5 2 10
1 2 3 4 5
1 5 1 5 1

Ghi chú:

  • 50% test có \( n \leq 5000 \)
  • 50% test có \( 5000 < n \leq 10^5 \)

Bình luận

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