Ý tưởng

• Ta thấy mỗi lần cải thiện chỉ tăng ~1~ điểm và cần viết ~b_i~ bài luận. Vì thế để tối ưu ta cần phải chọn cải thiện những bài kiểm tra có số bài luận cần viết là nhỏ nhất.
• Cài đặt:
  • Dùng sort để sắp xếp lại các bài kiểm tra theo số lượng bài luận cần viết.
  • Duyệt lần lượt qua các bài luận cho đến khi tổng điểm của ~n~ bài kiểm tra lớn hơn hoặc bằng ~avg~ thì dừng lại (nếu gặp bài kiểm tra đạt điểm ~10~ thì bỏ qua).

Code tham khảo

int n, avg;
pair<int, int> a[100005];
long long ans = 0, sum = 0;

int cmp(const ii &a, const ii &b){
    return a.second < b.second;
}

int main(){
    cin >> n >> avg;
    sum = 1LL*n*avg;
    for(int i = 1; i <= n; i++){
        cin >> a[i].first >> a[i].second;
        sum -= a[i].first;
    }

    sort(a+1, a+1+n, cmp);
    for(int i = 1; i <= n; i++){
        if (sum <= 0) break;
        if (a[i].first == 10) continue;
        sum--;
        ans += a[i].second;
    }
    if (sum > 0) cout << "khong the"; else cout << ans;
    return 0;
}