Cod sursa(job #429636)

Utilizator sdnxptVasiliu Radu sdnxpt Data 30 martie 2010 12:37:59
Problema Gutui Scor 70
Compilator cpp Status done
Runda teme_upb Marime 1.5 kb
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <algorithm>

using namespace std;


class Gutuie{
    public:
        unsigned int greutate, inaltime;
};

bool comp(Gutuie a, Gutuie b){
    return a.inaltime > b.inaltime;
}

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


int main(){
    unsigned int n, hmax, u;
    FILE * fin = fopen( "gutui.in", "r" );
    FILE * fout = fopen( "gutui.out", "w" );
    fscanf( fin, "%u %u %u", &n, &hmax, &u );
    unsigned int i, j;
    vector<Gutuie> v(n);
    for(i = 0; i < n; i++)
        fscanf(fin, "%u %u", &v[i].inaltime, &v[i].greutate);

    sort( v.begin(), v.end() , comp);
    //printf("%d\n", nivmax);
    /*for(i = 0; i < n; i++)
        printf("%d %d\n", v[i].inaltime, v[i].greutate);*/
    vector<unsigned int> max1(n + 1);
    vector<unsigned int> max2(n + 1);
    unsigned int k = 1;
    if( v[0].inaltime <= hmax ) {
        max1[1] = v[0].greutate;
        k = 1;
    }
    for(i = 2; i <= n; i++){
        for(j = 0; j <= k; j++){
            if( v[i - 1].inaltime + j * u <= hmax )
                max2[j + 1] = max( max1[j] + v[i - 1].greutate, max1[j + 1] );
            else
                break;
        }
        if( max2[k] )
            k++;
        for(j = 0; j <= k; j++)
            max1[j] = max2[j];
    }
    unsigned int maxim = 0;
    for(i = 0; i < k; i++)
        if( max1[i] > maxim )
            maxim = max1[i];

    fprintf(fout, "%d\n", maxim);

    fclose(fout);
    fclose(fin);
    return 0;
}