Cod sursa(job #432989)

Utilizator alexqawsFasui Alexandru alexqaws Data 3 aprilie 2010 03:20:52
Problema Gutui Scor 10
Compilator cpp Status done
Runda teme_upb Marime 4.14 kb
#include <iostream>
#include <fstream>
#include <stdlib.h>

using namespace std;

typedef struct gs{
    int hg;
    int gg;
    int ig;
} gs;


int n,h,u;
gs *gt;
int *g;
int nrg = 0;
int *ng;
int **niv;
int *p;
int *q;

int gmax = 0;
int nivmax = 0;

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

int print_niv(int **a, int *b){
    int i,j;
    cout<<endl;
    for(i=nivmax;i>=0;i--){
        cout<<i<<".  ";
        for(j=0;j<b[i];j++){
            cout<<a[i][j]<<" ";
        }
        cout<<endl;
    }
    cout<<endl;
    return 0;
}

int get_gmax(){
    int i,j;
    int k = 0;
    int c;
    for(i=nivmax;i>=0;i--){

        k++;
        j = 0;
        while(j<p[i]){
            /* nu e bine asa*/
             
            cout<<"i = "<<i<<", j = "<<j<<", g = "<<g[niv[i][j]]<<", k = "<<k<<", gt.gg = "<<gt[niv[i][j]].gg<<endl;
            c = 0;
            for(int iq = 0; iq<g[niv[i][j]]; iq++){ /* ineficient */
                if(q[iq]>0){
                    c  = c + 1;
                }
            }
            
            if(g[niv[i][j]] - c <= k){
                cout<<"gt[i].gg = "<<gt[niv[i][j]].gg<<", i = "<<i<<", j = "<<j<<endl;
                gmax = gmax + gt[niv[i][j]].gg;
                
                ng[g[niv[i][j]]]--;
                if(ng[g[niv[i][j]]]<=0){
                    q[g[niv[i][j]]]++;
                    cout<<"q => "<<g[niv[i][j]]<<endl;
                }
                j++;
                k--;
            }
            else{
                break;
            }
            if(k==0)
                break;
        }
        
        for(j=0;j<p[i];j++){/* ineficient */
            ng[g[niv[i][j]]]--;
            if(ng[g[niv[i][j]]]<=0){
                q[g[niv[i][j]]]++;
                cout<<"q => "<<g[niv[i][j]]<<endl;
            }
        }
        
        
    }
    return 0;
}

int read_vec(){
    ifstream fin;
    int i,last=0;
    
    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);
    //cout<<"n = "<<n<<"   h = "<<h<<"   u = "<<u<<endl;
    //cout<<"g = "<<nivmax<<endl;
    
    niv = (int **)malloc( nivmax * sizeof( int *));
    
    p = (int *)malloc( nivmax * sizeof( int ));
    
    g = (int *)malloc( n * sizeof( int ));
    ng = (int *)malloc( n * sizeof( int ));
    q = (int *)malloc( n * sizeof( int ));
    
    for (i=0;i<=nivmax;i++){
        niv[i] = (int *)malloc( n * sizeof( int ));
        p[i] = 0;
    }  
    
    for(i=0;i<n;i++){
        fin>>gt[i].hg;
        fin>>gt[i].gg;
        
        gt[i].hg = (gt[i].hg / u) + ( (gt[i].hg % u == 0) ? 0 : 1 ) ;
        
    }  
    
    qsort (gt, n, sizeof(gs), compare);
    
    
    
    for(i = 0; i < n; i++){
        
        q[i] = 0;
        
        niv[gt[i].hg][p[gt[i].hg]++] = i;
        
        if(i==0){
            g[0] = 0;
            ng[0] = 1;
            last = 0;
        }
        else{
            if(gt[i-1].gg == gt[i].gg){
                g[i] = g[i-1];
                ng[last]++;
            }
            else{
                g[i] = g[i-1] + 1;
                last++;
                ng[last] = 1;
            }
        }
        
        //cout<<"hg = "<<gt[i].hg<<"  gg = "<<gt[i].gg<<endl;
    }
    
    nrg = last + 1;
    
    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();
    //print_mat(m);
    
    //det_maxp();
    //print_mat(m);
    
    //read_mat();
    
    //det_maxr();
    //print_mat(m);
    
    //print_vec(hg);
    //print_vec(gt);
    

    print_niv(niv,p);
    
    get_gmax();
    
    write_sol();
    
    //cout<<"gmax ="<< gmax;

    //print_mat(mr);
    //cout<<"lp= "<<lp<<"  np= "<<np<<endl;
    //cout<<"lr= "<<lr<<"  nr= "<<nr<<endl;
    
    cin.get();//to_comment
        
    return 0;
}