문제 http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=1845&sca=3050


속도차이가 10배 이상 차이나는데 그 이유를 모르겠음 ㅠㅠ


=============================== 내 소스 ==============================================================

#include <stdio.h>

int N,S;

int H[300001];

int C[300001];

int dp[300001] = { 0, };

int index[300001];


int main()

{

int i, j, k, h;

scanf("%d %d",&N,&S);

for (i = 1; i <= N; i++){

scanf("%d %d", &H[i], &C[i]);

}

sort(1,N);


index[0] = 0;

for (i = 1; i <= N; i++){

for (j = index[i - 1]; j <= i; j++){

if (H[i] - S < H[j])break;

}

index[i] = j - 1;

}





for (i = 1; i <= N; i++){

if (dp[i - 1] > dp[index[i]] + C[i]){

dp[i] = dp[i - 1];

}

else{

dp[i] = dp[index[i]] + C[i];

}

}

printf("%d",dp[N]);



return 0;

}



int sort(int a, int b){

int T = a, i, P = b, temp;

if (a >= b)return 0;

for (i = a; i <= b; i++){

if (H[i] < H[P]){

temp = H[i]; H[i] = H[T]; H[T] = temp;

temp = C[i]; C[i] = C[T]; C[T] = temp;

T++;

}


}

if (H[T] > H[P]){

temp = H[T]; H[T] = H[P]; H[P] = temp;

temp = C[T]; C[T] = C[P]; C[P] = temp;

}


sort(a, T-1);

sort(T+1, b);


return 0;

}



=============================== 해답 ==============================================================


#include<stdio.h> #include<algorithm> #define MAX_N 300000 int d[MAX_N+1], max[MAX_N+1], idx[MAX_N+1]; int N, H, K; struct LIST {     int h, cost; } list[MAX_N+1]; struct SORTF {     bool inline operator () (LIST a, LIST b)     {         return a.h < b.h;     } }; int main() {     int i;     scanf("%d %d", &N, &H);     for(i = 1; i <= N; i++) scanf("%d %d", &list[i].h, &list[i].cost);     std::sort(list+1, list+1+N, SORTF());     for(i = 1; i <= N; i++)     {         for(idx[i] = idx[i-1] + 1; idx[i] < i; idx[i]++)             if(list[i].h - list[idx[i]].h < H) break;         idx[i]--;     }     for(i = 1; i <= N; i++)     {         d[i] = max[idx[i]] + list[i].cost;         max[i] = max[i-1] > d[i] ? max[i-1] : d[i];     }     printf("%d", max[N]);     return 0; }