ÀÛ¼ºÀÏ : 18-05-21 00:07
2012 Áß2 Àü½ÃÀå
 ±Û¾´ÀÌ : ¾çÁøÇõ(yangjh05)
Á¶È¸ : 2,595  
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>

using namespace std;

struct picture{
    int h;
    int money;
}H[300100];

int ptr = -1;
int N, S;
int D[300100];

bool cmp(picture A, picture B){
    return A.h < B.h;
}

int Fd_max(int HM){
    if(HM < H[0].h) return ptr = -1;
    if(ptr == -1) ptr = 0;
    for(int i = ptr; i < N; i++){
        if(HM < H[i].h) return ptr = i - 1;
    }
}

int max(int a, int b){
    return a < b? b : a;
}

void Fl_dyn(){
    D[0] = H[0].money;
    for(int i = 1; i < N; i++){
        int X = Fd_max(H[i].h - S);
        if(X == -1) D[i] = max(D[i - 1], H[i].h);
        else {
            int x = ptr;
            D[i] = max(D[i - 1], D[x] + H[i].money);
        }
    }
}

int main()
{
    scanf("%d %d", &N, &S);
    for(int i = 0; i < N; i++){
        scanf("%d %d", &H[i].h, &H[i].money);
    }
    sort(H, H + N, cmp);
    Fl_dyn();
    printf("%d\n", D[N - 1]);
    return 0;
}
//¼±»ý´ÔÀÌ °­ÀÇÇØÁֽŴë·Î Äڵ带 Â¥ ºÃ´Âµ¥¿ä... ¾îµð°¡ Ʋ·Á¼­ 30Á¡Àϱî¿ä?

ÄĽºÄð 18-05-24 21:30
 
¿­½ÉÈ÷ Çϸ鼭 ½Ç·Âµµ »ó´çÈ÷ ´Ã°í Àִ°Š°°½À´Ï´Ù.
ÇÏÁö¸¸ »ç¼ÒÇÑ ¿À·ù´Â °¡´ÉÇÏ¸é µð¹ö±ëÀ» ÅëÇØ ½º½º·Î ¹®Á¦¸¦ ãÀ¸·Á°í ³ë·ÂÀ» ÇØ¾ß ÇÕ´Ï´Ù.
±×·¯Áö ¾Ê°í¼­´Â ÇѰ踦 ¹þ¾î³¯ ¼ö ¾ø½À´Ï´Ù.

if(X == -1) D[i] = max(D[i - 1], H[i].h);
ÀÌ ºÎºÐ¿¡¼­ H[i].h°¡ ´«¿¡ µé¾î¿À³×¿ä.
°°Àº ½ÄÀÇ ´Ù¸¥ °÷¿¡¼­´Â H[i].money¸¦ ½è´Âµ¥ µÑ Áß Çϳª´Â À߸øµÈ °ÍÀÌ°ÚÁö¿ä?
 
 

Total 662
¹øÈ£ Á¦   ¸ñ ±Û¾´ÀÌ ³¯Â¥ Á¶È¸
622 ÀÚ±âÁÖµµ C¾ð¾î ÇÁ·Î±×·¡¹Ö 6´Ü¿ø 118p ÀÚ°¡Áø´Ü4 (1) ±è¿¬¿õ 06-19 2519
621 °áÁ¦Çß½À´Ï´Ù. È®ÀκÎŹµå¸³´Ï´Ù. Á¶¿µÀç 06-09 2648
620 °áÁ¦ ¿Ï·á ÇÏ¿´½À´Ï´Ù. È®ÀκÎŹµå¸³´Ï´Ù. (1) ¾ÈÁ¤Àº 05-24 2542
619 ÀÚ±âÁÖµµ C¾ð¾î ÇÁ·Î±×·¡¹Ö Çü¼ºÆò°¡ ¼Ò½º (1) ±è¿µÁÖ 05-14 2965
618 ÀÔ±ÝÇß½À´Ï´Ù~ (1) ÀÌ¿©Áø 04-05 2464
617 °áÁ¦¿Ï·áÇÏ¿´½À´Ï´Ù~ (1) ±è¹ÎÁÖ 02-10 2867
616 ÀÚ±âÁÖµµ C¾ð¾î ÇÁ·Î±×·¡¹Ö ±³Àç pdfÆÄÀÏÀ» ¾òÀ» ¼ö ÀÖÀ»±î¿ä? (2) Á¤¿ë±Õ 01-06 4454
615 ¹è¿­1¿¡¼­ ÀÚ°¡Áø´Ü7 (1) ±è¼¼¿¬ 11-01 3337
614 °áÀçÇß½À´Ï´Ù ±è¼ºÈñ 10-30 2911
613 2019³â ¹®Á¦Ç®ÀÌ ¿Ã·ÁÁÖ¼¼¿ä. (³»¿ë¹«) ¹ÚÁß¼ö 10-27 2815
612 °áÁ¦ ¹®ÀÇ ÇÑÁöÇö 10-05 3033
611 ¹æ±Ý ÀÔ±ÝÇß½À´Ï´Ù. Á¤¹ÎÁ¤ 08-23 2816
610 Ȥ½Ã 2008³â º»¼± Áß5 Æò¸éµµ ¹®Á¦ Ç®ÀÌ ¿Ã¶ó ¿Ô³ª¿ä? (1) À̹Π06-11 3291
609 ¼ö°­½ÂÀκÎŹµå¸³´Ï´Ù. (1) ¹éÇö¹Î 05-10 2953
608 ½ÂÀιٶø´Ï´Ù.ÀԱݿϷá. (1) ÀÌÀçÁØ 04-19 3054
607 À۳⵵ ¿¹¼±°ú Àü±¹º»¼± Ç®ÀÌ´Â ¾ðÁ¦Âë? (1) À̹ÌÈ­ 04-01 3036
606 ÀÔ±Ý È®ÀÎ ºÎŹµå¸³´Ï´Ù (1) ·ùÁö¹Î 03-17 2688
605 ÀÚ±âÁÖµµ C¾ð¾î °­Á½Åû (1) ŹÁø¾Æ 02-09 3067
604 °áÀç ½ÂÀÎ ¿äû (1) ½Å¹Î±Õ 02-09 2635
603 ¾Ë°í¸®Áò °­ÀÇ ½ÅûÇÒ·Á°í ÇÕ´Ï´Ù. (1) À̽ÂÅ 01-15 3015
 1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25  26  27  28  29  30    

ȸ»ç¼Ò°³ | °³ÀÎÁ¤º¸Ã³¸®¹æħ | ÀÌ¿ë¾à°ü | ã¾Æ¿À½Ã´Â ±æ | À̸ÞÀÏÁÖ¼Ò ¹«´Ü¼öÁý°ÅºÎ | »ç¾÷ÀÚÁ¤º¸È®ÀÎ
°æ±âµµ ¾È¾ç½Ã µ¿¾È±¸ È£°èµ¿ 1065-10 Çù¼º°ñµåÇÁ¶óÀÚ 601È£ ÇÑÄÄ¿¡µàÄÉÀ̼Ç(ÁÖ) TEL : 031-388-8840 FAX : 031-388-0996
´ëÇ¥ÀÚ : ±èµ¿±Ô »ç¾÷ÀÚ¹øÈ£ : 130-86-02870 Åë½ÅÆǸž÷½Å°í¹øÈ£ : Á¦ 2010-°æ±â¾È¾ç-888È£
COPYTIGHT(C) ÇÑÄÄ¿¡µàÄÉÀ̼Ç(ÁÖ), ALL RIGHT RESERVED.
´ãÀº°­Á : 0