Subtask 1, 2: ~1 \leq n, P, Q \leq 1000~.

Gọi ~f[i][j]~ là sản lượng lớn nhất đến ngày thứ ~i~ và đã trồng ~j~ hạt giống.

Trường hợp cơ bản: ~f[i][j] = a_i * j~ ~\forall i \leq k~.

Chuyển trạng thái:

• Không trồng: ~f[i][j] = f[i - 1][j]~.
• Trồng ~x~ cây: ~f[i][j] = \max(f[i - k][j - x] + a_i * x)~ ~\forall 1 \leq x \leq min(j, P)~.

Độ phức tạp ~\approx O(n.P.Q)~.

Subtask 3: ~1 \leq n, P, Q \leq 10^4~.

Tối ưu: Giả sử rằng ta trồng ở các vị trí ~i_1, i_2, \dots, i_k~. Tồn tại hoán vị ~p~ thỏa mãn ~a_{p_1} \geq a_{p_2} \geq \dots \geq a_{p_k}~. Khi này, rõ ràng với các giá trị ~a_i~ lớn, ta dùng ~P~ hạt sẽ tối ưu và phần còn dư sẽ dồn vào giá trị chưa được dùng.

Hay nói cách khác, khi chuyển trạng thái trồng ~x~ cây, ta chỉ quan tâm đến trồng đủ ~P~ hạt hoặc trồng phần còn dư đó là ~x = j \mod P~ và ~x = \min(j, P)~.

Độ phức tạp: ~O(n.Q)~.

Code tham khảo:

auto maxPlant = [&](int i) {
    return p * (((i - 1) / k) + 1);
};

FOR(i, 1, n) FOR(j, 1, min(q, maxPlant(i))) {
    f[i][j] = f[i - 1][j];
    if (i <= k) maximize(f[i][j], a[i] * j);
    else {
        int cur = min(j, p);
        maximize(f[i][j], f[i - k][j - cur] + a[i] * cur);

        cur = j % p;
        maximize(f[i][j], f[i - k][j - cur] + a[i] * cur);
    }
}