Cod sursa(job #433004)

Utilizator alexqawsFasui Alexandru alexqaws Data 3 aprilie 2010 05:46:09
Problema Gutui Scor 0
Compilator cpp Status done
Runda teme_upb Marime 2.43 kb
#include <iostream>
#include <fstream>
#include <stdlib.h>

using namespace std;

typedef struct gs{
    unsigned int ng;
    unsigned int gg;
    unsigned int hg;
} gs;

unsigned int n,h,u;
gs *gt;
unsigned int *luate;
unsigned int nr_luate = 0;

unsigned int p;

unsigned int gmax = 0;
unsigned int nivmax = 0;
unsigned int nivmin = 1000000;

int compare (const void * a, const void * b)
{
    return ( ((gs *)b)->gg - ((gs *)a)->gg);
}

int get_gmax(){
    //cout<<"nivmax = "<<nivmax<<", nivmin = "<<nivmin<<", p = "<<p<<", n = "<<n<<endl;
    unsigned int i,j;
    unsigned int k;
    for(i=0;i<p;i++){
        if(i==n){
            break;
        }
        if(gt[i].hg>h){
            continue;
        }
        k = 0;
        for(j=0;j<nr_luate;j++){ /* cate s-au luat de "mai sus" */
            if(luate[j] >= gt[i].ng){
                k++;
            }
        }
        
        //cout<<"nivmax = "<<nivmax<<", gt.ng = "<<gt[i].ng<<", gt.gg = "<<gt[i].gg<<", k = "<<k<<endl;
        
        if(nivmax + 1 - gt[i].ng - k > 0 ){
            luate[nr_luate++] = gt[i].ng;
            gmax = gmax + gt[i].gg;
            //cout<<"h = "<<gt[i].ng<<",   g = "<<gt[i].gg<<endl;
        }
        else{
            p++;
        }
    }
    
    return 0;
}

int read_vec(){
    ifstream fin;
    unsigned int i;
    
    fin.open("gutui.in",ios::in);
    
    fin>>n;
    fin>>h;
    fin>>u;
    
    gt = (gs *)malloc( n * sizeof( gs ));  
    
    //nivmax = h / u + ( ( h % u == 0) ? 0 : 1 ) ;
    nivmax = h / u + 1;

    for(i=0;i<n;i++){
        fin>>gt[i].hg;
        fin>>gt[i].gg;
        
        //gt[i].ng = (gt[i].hg / u) + ( (gt[i].hg % u == 0) ? 0 : 1 ) ;
        gt[i].ng = (gt[i].hg / u) + 1;
        if(gt[i].ng < nivmin){
            nivmin = gt[i].ng;
        }
    }  
    
    //p = nivmax - nivmin + 1;
    p = nivmax - nivmin ;
    
    if(p > n){
        p = n;
    }
    
    luate = (unsigned int *)malloc( p * sizeof( int ));
    
    qsort (gt, n, sizeof(gs), compare);
    
    fin.close();
    return 0;
}


int write_sol(){
    ofstream fout;
    fout.open("gutui.out",ios::out);
    
    fout<<gmax;
    
    fout.close();
    return 0;
}

int main(){
     
    read_vec();  
    
    get_gmax();
    
    write_sol();
    
    //cout<<endl<<"gmax = "<< gmax;
    
    //cin.get();//to_comment
        
    return 0;
}