2515번: 전시장

https://www.acmicpc.net/problem/2515


$O(n\lg n)$

그림(hi,ci)를 h를 기준으로 오름차순 정렬한다.
dp[n]: 1~n 그림을 가지고 남길 수 있는 최대 이익
dp[n]=max(dp[n-1],dp[p]+cn) (p는 hx<=hi-s를 만족하는 최대 x)

#include<cstdio>
#include<algorithm>
using namespace std;
const int MXN = 3e5;
int n, s, dp[MXN + 1];
pair<int, int> p[MXN + 1];
int main() {
    scanf("%d%d", &n, &s);
    for (int i = 1; i <= n; i++) scanf("%d%d", &p[i].first, &p[i].second);
    sort(p + 1, p + 1 + n);
    for (int i = 1, j = 0; i <= n; i++) {
        while (p[j + 1].first <= p[i].first - s) j++;
        dp[i] = max(dp[i - 1], dp[j] + p[i].second);
    }
    printf("%d", dp[n]);
    return 0;
}