- Nhận thấy khoảng cách xuất từ một vị trí bất kì không được vượt quá k ⇒ k = 2×k+1

- Thuật toán như sau: Lưu lại tọa độ và số cây nấm vào một mảng, nếu đặt k là một của sổ thì ta sẽ chỉ cần tính tổng của mỗi của sổ có độ dài k, đây gọi là thuật toán sliding window rất phổ biến

- Độ phức tạp: O(max_xi)

- Code:

#include <bits/stdc++.h>
#define ll long long
const int maxn = (int) 1e7;
using namespace std;
int a[maxn];
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n, k, max_x, sum = 0, ans = 0; cin >> n >> k;
    memset(a,0,sizeof(a));
    for (int i = 0; i < n; i++){
        int c, x; cin >> c >> x;
        a[x] = c;
        max_x = max(x,max_x);
    }
    k = 2*k+1;
    for (int i = 0; i < k; i++)
        sum += a[i];
    if (k > max_x)
        cout << sum << '\n';
    else{
        for (int i = k; i < max_x+1; i++){
            sum = sum + a[i] - a[i-k];
            ans = max(ans, sum);
        }
        cout << ans << '\n';
    }
    return 0;
}