Tóm tắt đề bài

Có \(N\) bức tranh, bức \(i\) có kích thước \(A_i\) và giá trị \(B_i\). Chọn ít nhất một bức để trưng bày, gọi:

• \(A_{\min}\): kích thước nhỏ nhất trong nhóm chọn
• \(A_{\max}\): kích thước lớn nhất trong nhóm chọn
• \(S\): tổng giá trị \(B\) của các bức được chọn

Lợi nhuận:

Hãy tìm \(H\) lớn nhất.

Phân tích

• \(N \le 500000\) nên cần thuật toán khoảng \(O(N \log N)\) hoặc tốt hơn.
• Nếu ta sắp xếp các bức theo kích thước \(A\) tăng dần, thì với một tập được chọn, \(A_{\min}\) và \(A_{\max}\) chính là kích thước ở hai đầu đoạn chỉ số nào đó trong mảng đã sắp xếp.
• Nhận xét quan trọng:
  • Với hai đầu \(l, r\) (\(l \le r\)), để tối đa \(S\) khi \(A_{\min}=A_l\), \(A_{\max}=A_r\), ta luôn nên lấy tất cả các bức trong đoạn \([l..r]\) (vì mọi \(B_i \ge 1\), thêm tranh chỉ tăng \(S\) mà không đổi \(A_{\min}, A_{\max}\)).
  • Do đó bài toán trở thành: chọn một đoạn liên tiếp sau khi sort theo \(A\) để tối đa

Hướng giải quyết

Biến đổi công thức

Sau khi sort theo \(A\) tăng dần, đặt mảng \(a[i] = (A_i, B_i)\) theo thứ tự mới. Dùng tổng tiền tố:

Khi đó:

Suy ra:

Với mỗi \(r\) cố định, để tối đa \(H(l,r)\) ta cần chọn \(l\) sao cho \((pref[l-1] - A_l)\) là nhỏ nhất.

Thuật toán (đúng như code AC)

1. Đọc \(N\), đọc các cặp \((A_i, B_i)\).
2. Sắp xếp theo \(A\) tăng dần.
3. Tính mảng \(pref\).

4. Duyệt \(r\) từ \(1\) đến \(N\):

   • Cập nhật:

     \[minVal = \min(minVal,\ pref[r-1] - A_r)\]

     (đây chính là giá trị nhỏ nhất của \(pref[l-1]-A_l\) với \(l \le r\))

   • Tính lợi nhuận tốt nhất kết thúc tại \(r\):

     \[cur = (pref[r] - A_r) - minVal\]

   • Cập nhật đáp án \(ans = \max(ans, cur)\).

   • In \(ans\).

Trực giác

• Ta đang tối ưu một “đoạn con tốt nhất” sau khi sort theo \(A\).
• Công thức đã tách \(H(l,r)\) thành “phần phụ thuộc \(r\)” trừ đi “phần phụ thuộc \(l\)”.
• Khi quét \(r\) từ trái sang phải, ta chỉ cần nhớ “điểm bắt đầu tốt nhất” (tức giá trị nhỏ nhất của \(pref[l-1]-A_l\)) để ghép với \(r\) hiện tại.

Lưu ý / bẫy thường gặp

• Giá trị có thể rất lớn: \(A_i\) tới \(10^{15}\), \(pref\) có thể tới \(5 \cdot 10^{14}\), nên phải dùng long long.
• Bắt buộc chọn ít nhất một bức: thuật toán vẫn đúng vì xét cả trường hợp \(l=r\) (khi đó \(H = B_r\)).
• Sort theo \(A\) là bắt buộc để đảm bảo \(A_{\min}, A_{\max}\) tương ứng hai đầu đoạn.

Độ phức tạp

• Thời gian: \(O(N \log N)\) do sắp xếp, phần quét là \(O(N)\).
• Bộ nhớ: \(O(N)\) cho mảng và prefix sum.

Code tham khảo

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;

    // a[i] = (A_i, B_i), dùng 1-index theo đúng code AC
    vector<pair<long long, long long>> a(N + 1);
    for (int i = 1; i <= N; i++) {
        cin >> a[i].first >> a[i].second;
    }

    // Sắp xếp theo kích thước A tăng dần
    sort(a.begin() + 1, a.end());

    // Prefix sum giá trị B
    vector<long long> pref(N + 1, 0);
    for (int i = 1; i <= N; i++) {
        pref[i] = pref[i - 1] + a[i].second;
    }

    long long ans = 0;
    long long minVal = LLONG_MAX;

    // Quét r và duy trì min(pref[l-1] - A[l])
    for (int r = 1; r <= N; r++) {
        // xét l = r để cập nhật minVal (và mọi l < r đã được xét trước đó)
        minVal = min(minVal, pref[r - 1] - a[r].first);

        // H tốt nhất với đoạn kết thúc tại r:
        // H = (pref[r] - A[r]) - minVal
        long long cur = (pref[r] - a[r].first) - minVal;
        ans = max(ans, cur);
    }

    cout << ans;
    return 0;
}