Cod sursa(job #432984)

Utilizator sdnxptVasiliu Radu sdnxpt Data 3 aprilie 2010 01:28:03
Problema Gutui Scor 100
Compilator cpp Status done
Runda teme_upb Marime 1.91 kb
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <algorithm>

using namespace std;

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

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

bool comp2(unsigned int a, unsigned int b){
    return a > b;
}

inline unsigned int nivel( unsigned int a, unsigned int u, unsigned int hmax ){
    if( a % u <= hmax % u )
        return a / u;
    else
        return a / u + 1;
}

int main(){
    unsigned int n, u, hmax;
    FILE * fin = fopen( "gutui.in", "r" );
    FILE * fout = fopen( "gutui.out", "w" );
    fscanf( fin, "%u %u %u", &n, &hmax, &u );
    unsigned int i, x, y;
    vector<Gutuie> v(n);
    for(i = 0; i < n; i++){
        fscanf(fin, "%u %u", &x, &y);
        v[i].greutate = y;
        v[i].nivel = nivel(x, u, hmax);
    }
    sort( v.begin(), v.end(), comp1 );
    unsigned int nivmax = nivel(hmax, u, hmax), niv = v[0].nivel, nr = 0;
    vector<unsigned int> greutate;
    for(i = 0; i < n; i++){
        if( v[i].nivel == niv ){
            if( nr < nivmax - niv + 1 ){
                nr ++;
                greutate.push_back( v[i].greutate );
            }
        }
        else{
            inplace_merge( greutate.begin(), greutate.end() - nr, greutate.end(), comp2 );
            greutate.resize( nivmax - niv + 1 );
            niv = v[i].nivel;
            nr = 0;
            i --;
        }
    }
    inplace_merge( greutate.begin(), greutate.end() - nr, greutate.end(), comp2 );
    greutate.resize( nivmax - niv + 1 );
    unsigned int gmax = 0;
    for(i = 0; i < greutate.size(); i++)
        gmax += greutate[i];
    fprintf(fout, "%u\n", gmax);
    fclose(fout);
    fclose(fin);
    return 0;
}