Cod sursa(job #1856326)

Utilizator CodrutLemeniCodrut Lemeni CodrutLemeni Data 24 ianuarie 2017 19:24:29
Problema Peste Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.42 kb
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <string.h>
#include <queue>
#define N 50100
#define INF -1
#define T 1001


using namespace std;


struct plasa {
    int p , t ;
};

plasa pls [ N ] ;
int fish [ N ] ;
int best [ N ] ;
long long sol [ N ];

bool cmp ( plasa a , plasa b ){
    return a.t < b.t ;
}

priority_queue < int > que ;

int main(){
    int n , k , tmax , i , j ,id ;
    int sum = 0 ,tpls = 0 ;

    freopen("peste.in","r",stdin );
    freopen("peste.out","w",stdout );

    scanf("%d%d%d", &n , &k , &tmax );

    for ( i = 0 ; i < n ; i ++ ){
        scanf("%d%d",&pls[ i ].p , &pls [ i ].t );

        if ( pls [ i ].t > tpls ){
            tpls = pls [ i ].t ;
        }

    }


    sort ( pls , pls + n , cmp );

    int nr = 0 , nrp  ;
    for ( i  = 0 , nrp = 0 ; i <= tpls ; i ++ ){

        while ( pls[ nrp ]. t == i && nrp < n ){
            sum += pls [ nrp ] . p ;

            que. push ( -pls [ nrp ]. p );

            nr ++ ;

            nrp ++ ;
        }


        while ( nr > k ){
            sum += que.top();
            que.pop() ;
            nr-- ;
        }

        best [ i ] = sum ;

    }

    for ( i = 0 ; i <= tmax ; i ++ ){
        sol [ i ] = INF ;
    }

    sol [ 0 ] = 0 ;
    for ( i = 0 ; i <=  tmax ; i  ++ ){

        for ( j = 1 ; j <= tpls && i - j >= 0  ; j ++ ){
            sol[ i ] = max ( sol [ i ] , sol [ i - j ] + best [ j ] );
        }



//        for ( j = tmax - pls [ i ] .t ; j >=0 ; j -- ){
//
//            if ( sol [ j ] == INF ){
//                continue ;
//            }
//
//            if ( sol[ j + pls [ i ].t ] < sol [ j ] + best [ i ] ){
//                sol[ j + pls [ i ].t ] = sol [ j ] + best [ i ] ;
//            }
//
//            for ( id = j + 2 * pls [ i ].t  ; id <= tmax ; id += pls [ i ].t ){
//
//                if ( sol [ id ] < sol [ id - pls[ i ].t ] + best [ i ] ){
//                    sol [ id ] = sol [ id - pls[ i ].t ] + best [ i ] ;
//                }else {
//                    break ;
//                }
//
//            }
//
//        }

    }


    for ( i = 0 ; i <= tmax ; i ++ ){
        sol[ tmax ] = max ( sol [ i ] , sol [ tmax ] ) ;
    }


    if ( sol [ tmax ] == -1 ){
        printf("0");
        return 0 ;
    }

    printf("%lld",sol[ tmax ] );

    return 0;
}