Các lượt nộp
    Danh sách bài
    Trang chủ
    Báo lỗi

    solution

    Đề bài: [C] Khung K phiên giao dịch có tổng lợi nhuận cao nhất

    Một nhà đầu tư có nhật kí lợi nhuận theo nnn phiên: a0,a1,…,an−1a_0, a_1, \dots, a_{n-1}a0​,a1​,…,an−1​ (có thể âm). Anh ấy muốn chọn KKK phiên liên tiếp sao cho tổng lợi nhuận lớn nhất. Hãy in ra tổng lợi nhuận đó và chỉ số bắt đầu của đoạn (nếu có nhiều đoạn cùng tổng lớn nhất, chọn đoạn có chỉ số bắt đầu nhỏ nhất).

    Ví dụ: a=[1,2,3,4,5,1]a = [1, 2, 3, 4, 5, 1]a=[1,2,3,4,5,1], K=3K = 3K=3 ⇒ đoạn tốt nhất là [3,4,5][3,4,5][3,4,5] bắt đầu ở chỉ số 222, tổng 121212.

    • Định dạng đầu vào:
      • Dòng 1: hai số nguyên nnn và KKK.
      • Dòng 2: nnn số nguyên cách nhau dấu cách.
    • Ràng buộc đầu vào:

      1≤K≤n≤10001 \le K \le n \le 10001≤K≤n≤1000; −106≤ai≤106-10^6 \le a_i \le 10^6−106≤ai​≤106.

    • Định dạng đầu ra:

      Một dòng gồm hai số: tổng lớn nhất và chỉ số bắt đầu, cách nhau dấu cách.

    Ví dụ:

    Đầu vào:

    6 3
1 2 3 4 5 1

    Đầu ra:

    12 2

    Giải thích:

    Đoạn [3,4,5] có tổng 12, bắt đầu ở chỉ số 2.

    Đang tải editor...