AcWing 782. 双指针
原题链接
中等
作者:
史一帆
,
2021-04-29 16:24:58
,
所有人可见
,
阅读 338
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 200010;
typedef pair<int, int> PII;
PII a[N];
int main()
{
int n, d;
cin >> n >> d;
for (int i = 1; i <= n; i ++ ) cin >> a[i].first >> a[i].second;
sort(a + 1, a + 1 + n);
int res = 0;
for (int i = 1, j = 0, maxa = -1e9; i <= n; i ++ ) // maxa + a[].second必须 <= 0
{
while (j + 1 < i && a[i].first - a[j + 1].first >= d)
{
j ++ ;
maxa = max(maxa, a[j].second);
}
res = max(res, a[i].second + maxa);
}
cout << res << endl;
return 0;
}