Cod sursa(job #427550)

Utilizator sdnxptVasiliu Radu sdnxpt Data 27 martie 2010 23:27:58
Problema Gutui Scor 10
Compilator cpp Status done
Runda teme_upb Marime 1.88 kb
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <algorithm>

using namespace std;

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

bool operator<(Gutuie a, Gutuie b){
    return a.greutate > b.greutate;
}

unsigned int u;

inline unsigned int nivel( unsigned int a ){
    if( a % u == 0 )
        return a / u - 1;
    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;
    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() );

    vector<int> nrmax(n);
    unsigned int nivmax = nivel( hmax );
    for(i = 0; i < n; i++)
        nrmax[i] = nivmax - nivel( v[i].inaltime ) + 1;

    /*for(i = 0; i < n; i++)
        printf("%d %d %d\n", v[i].inaltime, v[i].greutate, nrmax[i]);*/

    unsigned int gmax = 0;
    vector<unsigned int> nrluat(n);
    for(i = 0; i < n; i++)
        if( nrmax[i] > 0 ){
            gmax += v[i].greutate;
            if( nrluat[i] ){
                for(j = 0; j < n; j++){
                    nrmax[j] --;
                    if( nivel(v[i].inaltime) == nivel(v[j].inaltime) )
                        nrluat[j] ++;
                }

            }
            else{
                for(j = 0; j < n; j++)
                    if( nivel(v[j].inaltime) == nivel(v[i].inaltime) ){
                        nrmax[j] --;
                        nrluat[j] ++;
                }
            }
            /*for(j = 0; j < n; j++)
                printf("%d ", nrmax[j]);
            printf("\n");*/
        }

    /*for(i = 0; i < n; i++)
        printf("%d %d %d\n", v[i].inaltime, v[i].greutate, nrmax[i]);*/
    fprintf(fout, "%u\n", gmax);
    fclose(fout);
    fclose(fin);
    return 0;
}