Pagini recente » Cod sursa (job #2435409) | Cod sursa (job #2192113) | Cod sursa (job #446085) | Cod sursa (job #2976238) | Cod sursa (job #433634)
Cod sursa(job #433634)
#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 *nivel;
int nr_luate = 0;
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;
int i,j;
unsigned int k;
for(i=0;i<p;i++){
if(i==n){
break;
}
if(gt[i].hg>h){
p++;
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 ){
//if(nivmax - 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;
int i, j;
int nvc;
unsigned int ic;
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; //????
nivmax = h / u;
nivel = (unsigned int *)malloc( (h + 1) * sizeof(unsigned int ));
//nvc = nivmax;
ic = h;
for(i = nivmax; i >=0 ;i--){
for(j = 0; j<u; j++){
//cout<<"ic = "<<ic<<", nivcur = "<<i<<endl;
if(ic>0)
nivel[ic--] = i;
}
}
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; //????
//gt[i].ng = (gt[i].hg / u);
gt[i].ng = nivel[ gt[i].hg ];
if(gt[i].ng < nivmin){
nivmin = gt[i].ng;
}
}
p = nivmax - nivmin + 1;
//p = nivmax - nivmin ; //????
//cout<<nivmax<<" "<<nivmin;
//mai bine pornesc de la h si scad multiplii de u
if(p > n){ //??
p = n;
}
luate = (unsigned int *)malloc( p * sizeof(unsigned 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;
}