Gợi ý

• Giả sử ta có ~k~ ngày để hoàn thành cuộc chơi, thì để đạt được số điểm lớn nhất ta có thể tham lam bằng cách ở mỗi lượt số đầu tiên được chọn sẽ là ~k~ số lớn nhất trong dãy, số thứ hai được chọn ở mỗi lượt sẽ là ~k~ số lớn nhất còn lại trong dãy, ...

Subtask 1

• Vì ~n < 5000~ nên ta có thể giả sử số lượt có thể hoàn thành cuộc chơi. Dùng ý tưởng ban đầu để tính toán xem có thể đạt được ~m~ điểm hay không.
• Độ phức tạp: ~O(n^2)~.

Subtask 2

• Vì ~m = a_{1} + a_{2} + ... + a_{n}~ nên ở mỗi lượt ta chỉ được chọn ~1~ số ~/to~ đáp án là ~n~.
• Độ phức tạp ~O(1)~.

Subtask 3

• Ta có thể tối ưu bằng cách dùng chặt nhị phân số ngày hoàn thành cuộc chơi.
• Độ phức tạp: ~O(nlogn)~

Code mẫu

#include <bits/stdc++.h>

using namespace std;
#define int long long

const int N = 2e5 + 5;
int n, m;
int a[N], Sum = 0;

void Input() {
    cin >> n >> m;
    for(int i = 1; i <= n; i++) cin >> a[i], Sum += a[i];
}

bool check(int mid) {
    if (mid == 0) return m==0;
    int sum = 0;
    for(int i = 1; i <= n; i++) {
        sum += max(a[i] - (i-1)/mid, 0LL);
    }
    return sum >= m;
}

void Solve() {
    if (Sum < m) {
        cout << "Impossible";
        return;
    }
    sort(a+1, a+1+n);
    reverse(a+1, a+1+n);
    int l = 0, r = n;
    int ans;
    while(l <= r) {
        int mid = (l + r) >> 1;
        if (check(mid)) {
            ans = mid;
            r = mid - 1;
        }
        else {
            l = mid + 1;
        }
    }
    cout << ans;
    return;
}

int32_t main() {
    Input();
    Solve();
    return 0;
}