KOI(한국정보올림피아드) 2012년 중등부2번 전시장

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

#include 
#include 
using namespace std;
#define MAX_N 300000

int N, S;
int sellprice[MAX_N+1]; //sellprice[1]부터 사용, 그림 i를 마지막으로 골랐을 때 최대 전체 판매 가격
int M[MAX_N+1]; //max(0~sellprice[i])
int k[MAX_N+1];

struct Picture {
    int height, cost;
    bool operator<(const Picture &p) const { return height < p.height; } //높이순으로 정렬
}picture [MAX_N+1];

void solve() {
    sort(picture+1, picture+N+1);

    for(int i=1; i<=N; i++) {
        k[i] = k[i-1];
        while(true) {
            if(k[i] >= 0) {
                if(picture[k[i]].height + S > picture[i].height) {
                    k[i]--;
                    break;
                }
            }
            if(k[i] == i-1) break;
            k[i]++;
        }
    }

    for(int i=1; i<=N; i++) {
        if(k[i] >= 0)
            sellprice[i] = picture[i].cost + M[k[i]];
        M[i] = max(M[i-1], sellprice[i]);
    }
    printf("%d", M[N]);
}
int main() {
    scanf("%d %d", &N, &S);
    for(int i=1; i<=N; i++)
        scanf("%d %d", &picture[i].height, &picture[i].cost);
    solve();
    return 0;
}