Pagini recente » Cod sursa (job #453325) | Cod sursa (job #3038745) | Cod sursa (job #2516540) | Cod sursa (job #127977) | Cod sursa (job #432987)
Cod sursa(job #432987)
#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;
}