Cod sursa(job #427336)

Utilizator sdnxptVasiliu Radu sdnxpt Data 27 martie 2010 19:06:27
Problema Gutui Scor 0
Compilator cpp Status done
Runda teme_upb Marime 2.33 kb
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <algorithm>

using namespace std;

unsigned int u;

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

inline unsigned int nivel( unsigned 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;
    }
}

inline unsigned int difinaltime( unsigned int a ){
    if( a % u == 0 )
        return u;
    else
        return a % u;
}

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].inaltime = 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 = v[0].nivel, nr = 0, nivmin = v[n - 1].nivel, nrmax;
    vector<unsigned int> greutati;
    for(i = 0; i < n; i++){
        nrmax = nivmax - niv;
        if( v[i].nivel == niv ){
            if( nr < nrmax ){
                greutati.push_back( v[i].greutate );
            }
            if( nr == nrmax && difinaltime( v[i].inaltime ) <= difinaltime( hmax ) ){
                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() );
    /*for(i = greutati.size(); i > 0; i--)
        printf("%d\n", greutati[i - 1]);*/
    unsigned int gmax = 0;
    j = 0;
    for(i = greutati.size(); i > 0 && j < nivmax - nivmin; i--, j++)
        gmax += greutati[i - 1];
    //printf("%d\n", gmax);
    fprintf(fout, "%u\n", gmax);


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