Cod sursa(job #427273)

Utilizator sdnxptVasiliu Radu sdnxpt Data 27 martie 2010 18:13:47
Problema Gutui Scor 30
Compilator cpp Status done
Runda teme_upb Marime 1.87 kb
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <algorithm>

using namespace std;

int u;

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

inline unsigned int nivel( int a ){
    /*if( a % u == 0 )
        return a / u - 1;
    else*/
        return a / u;
    }

bool operator<(Gutuie a, Gutuie b){
    if( a.nivel < b.nivel )
        return false;
    else{
        if( a.nivel == b.nivel ) {
            if( a.greutate < b.greutate )
                return false;
            else
                return true;
        }
        else
            return true;
    }
}


int main(){
    unsigned int n, hmax;
    FILE * fin = fopen( "gutui.in", "r" );
    FILE * fout = fopen( "gutui.out", "w" );
    fscanf( fin, "%u %u %u", &n, &hmax, &u );
    unsigned int i, j, x, y;
    vector<Gutuie> v(n);
    for(i = 0; i < n; i++){
        fscanf(fin, "%u %u", &x, &y);
        if( x <= hmax )
            v[i].nivel = nivel( x );
        v[i].greutate = y;
    }
    sort( v.begin(), v.end() );
    unsigned int nivmax = nivel( hmax );
    //printf("%d\n", nivmax);
    /*for(i = 0; i < n; i++)
        printf("%d %d\n", v[i].nivel, v[i].greutate);*/

    unsigned int niv = nivmax, nr = 0, nivmin = v[n - 1].nivel;
    vector<unsigned int> greutati;
    for(i = 0; i < n; i++){
        if( v[i].nivel == niv ){
            if( nr < nivmax - niv + 1 ){
                greutati.push_back( v[i].greutate );
                nr ++;
            }
        }
        else
            if( v[i].nivel < niv ){
                niv = v[i].nivel;
                nr = 0;
                i --;
            }
    }
    sort( greutati.begin(), greutati.end() );
    unsigned int gmax = 0;
    j = 0;
    for(i = greutati.size() - 1; i >= 0 && j < nivmax - nivmin + 1; i--, j++)
        gmax += greutati[i];
    fprintf(fout, "%u\n", gmax);


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