Cod sursa(job #437839)

Utilizator alexqawsFasui Alexandru alexqaws Data 10 aprilie 2010 04:13:35
Problema Gutui Scor 20
Compilator cpp Status done
Runda teme_upb Marime 3.42 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 h,u;
unsigned int n;
gs *gt;
unsigned int *q /* cate am luat de pe niv. respectiv */;
//unsigned int nr_luate = 0;

unsigned int p;

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

int compare (const void * a, const void * b)
{
    if( ((gs *)b)->gg != ((gs *)a)->gg ){
        if ( ((gs *)b)->gg > ((gs *)a)->gg ){
            return 1;
        }
        else{
            return -1;
        }
    }
    else{
        if( ((gs *)b)->hg > ((gs *)a)->hg ){
            return 1;
        }
        else
            if ( ((gs *)b)->hg < ((gs *)a)->hg ){
                return -1;
            }
            else{
                return 0;
            }
    }
}

int get_gmax(){
    unsigned int i, j, k, t, y, flag;
    
    for(i=0;i<p;i++){
        
        if(i==n){
            break;
        }
        if(gt[i].hg > h){
            p++;
            continue;
        }
        k = 0;
        t = 0;
        y = 0;
        flag = 1;
        
        /*
        for(j=gt[i].ng + 1; j<= nivmax;j++){
            k = k + nivmax + 1 - j - q[j];
        }*/
        
        y =  nivmax + 1 - gt[i].ng - q[gt[i].ng];
        
        
        for(j=0; j<= gt[i].ng - 1;j++){
            //cout<<nivmax + 1 - j << endl;
            if( q[j] == 0 ){
                flag = 0;
                break;
            }
        }
        //cout<<endl<<endl;
        
        /*
        TODO:
            -nu pot lua elementul curent daca am luat deja alte elemente care se afla "mai jos" ca el,
            consumandu-i astfel pozitia
        */
        
        
        if( ( q[gt[i].ng] > 0  ) && flag ){

            if(q[gt[i].ng] > 0){
                q[gt[i].ng]--;
            }
            
            for(j=0; j<= gt[i].ng - 1;j++){
                if( q[j] > 0 ){
                    q[j]--;
                }
            }

            gmax = gmax + gt[i].gg;

        }
        else{
            p++;
        }
    }
    
    return 0;
}

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

    for(i=0;i<n;i++){
        fin>>gt[i].hg;
        fin>>gt[i].gg;
        
        gt[i].hg = gt[i].hg + o;

        gt[i].ng = gt[i].hg / u;
        
        if(gt[i].ng < nivmin){
            nivmin = gt[i].ng;
        }
    }  
    
    p = nivmax - nivmin + 1;
    
    if(p > n){ //??
        p = n;
    }
    
    q = (unsigned int *)malloc( (nivmax + 1) * sizeof( unsigned int ));
    
    for(i=0;i<=nivmax;i++){
        q[i] = nivmax + 1 - i;
    }
    
    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();
    
    //cin.get();//to_comment
        
    return 0;
}