Cod sursa(job #424026)

Utilizator sdnxptVasiliu Radu sdnxpt Data 24 martie 2010 15:48:21
Problema Gutui Scor 10
Compilator cpp Status done
Runda teme_upb Marime 1.65 kb
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <algorithm>

using namespace std;

int u;

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

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

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


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

    i = 0;
    while( v[i].inaltime > hmax )
        i++;
    int niv = nivel(v[i].inaltime);
    int difniv = nivel(hmax) - niv;
    int inc = i;
    int gmax = 0;
    vector<int> greutati;
    for(i = inc; i < n;){
        niv = nivel(v[i].inaltime);
        gmax += v[i].greutate;
        i ++;
        while( nivel(v[i].inaltime) == niv )
            greutati.push_back( v[i ++].greutate );
    }
    sort( greutati.begin(), greutati.end() );
    int size = greutati.size();
    for(i = size - 1, j = 0; j < difniv; i --, j++)
        gmax += greutati[i];
    fprintf(fout, "%d\n", gmax);

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