ÀÛ¼ºÀÏ : 18-05-21 00:07
2012 Áß2 Àü½ÃÀå
 ±Û¾´ÀÌ : ¾çÁøÇõ(yangjh05)
Á¶È¸ : 545  
#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 616
¹øÈ£ Á¦   ¸ñ ±Û¾´ÀÌ ³¯Â¥ Á¶È¸
616 ¹è¿­1¿¡¼­ ÀÚ°¡Áø´Ü7 ±è¼¼¿¬ 11-01 82
615 °áÀçÇß½À´Ï´Ù ±è¼ºÈñ 10-30 101
614 2019³â ¹®Á¦Ç®ÀÌ ¿Ã·ÁÁÖ¼¼¿ä. (³»¿ë¹«) ¹ÚÁß¼ö 10-27 91
613 °áÁ¦ ¹®ÀÇ ÇÑÁöÇö 10-05 127
612 ¹æ±Ý ÀÔ±ÝÇß½À´Ï´Ù. Á¤¹ÎÁ¤ 08-23 204
611 Ȥ½Ã 2008³â º»¼± Áß5 Æò¸éµµ ¹®Á¦ Ç®ÀÌ ¿Ã¶ó ¿Ô³ª¿ä? (1) À̹Π06-11 346
610 ¼ö°­½ÂÀκÎŹµå¸³´Ï´Ù. (1) ¹éÇö¹Î 05-10 326
609 ½ÂÀιٶø´Ï´Ù.ÀԱݿϷá. (1) ÀÌÀçÁØ 04-19 394
608 À۳⵵ ¿¹¼±°ú Àü±¹º»¼± Ç®ÀÌ´Â ¾ðÁ¦Âë? (1) À̹ÌÈ­ 04-01 491
607 ÀÔ±Ý È®ÀÎ ºÎʵ右´Ï´Ù (1) ·ùÁö¹Î 03-17 406
606 ÀÚ±âÁÖµµ C¾ð¾î °­Á½Åû (1) ŹÁø¾Æ 02-09 545
605 °áÀç ½ÂÀÎ ¿äû (1) ½Å¹Î±Õ 02-09 427
604 ¾Ë°í¸®Áò °­ÀÇ ½ÅûÇÒ·Á°í ÇÕ´Ï´Ù. (1) À̽ÂÅ 01-15 552
603 ÀÔ±ÝÇß¾î¿ä (1) È«ÇõÀç 01-13 428
602 ¼ö°­½ÅÃ»ÇØ¼­ ÀÔ±ÝÀ» Çߴµ¥ °­Àǰ¡ ¾ø¾î¿ä.. (1) È«ÇõÀç 01-12 926
601 ÀÔ±ÝÈ®ÀÎ ºÎʵ右´Ï´Ù. (1) ±èÁø¼÷ 01-08 376
600 ÀÚ±âÁÖµµ C¾ð¾î ÇÁ·Î±×·¡¹Ö ¹Ýº¹Á¦¾î¹®2 Çü¼ºÆò°¡ 10 (1) À̼º¿ì 12-09 751
599 ÀÚ±âÁÖµµ c¾ð¾î ÇÁ·Î±×·¡¹Ö <ÀÔ·Â> ÀÚ°¡Áø´Ü 8¹ø Áú¹®ÀÔ´Ï¡¦ (1) Áø¼º±Ô 10-18 583
598    ÀÚ±âÁÖµµ c¾ð¾î ÇÁ·Î±×·¡¹Ö <ÀÔ·Â> ÀÚ°¡Áø´Ü 8¹ø Áú¹®ÀÔ´Ï¡¦ ÀÌÀçÀ± 11-04 599
597 ÀÚ±âÁÖµµ c¾ð¾î ÇÁ·Î±×·¡¹Ö <ÀÔ·Â>ÀÚ°¡Áø´Ü5¹ø Àß ¸ð¸£°Ú¡¦ (1) Áø¼º±Ô 10-18 473
 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