Pagini recente » Cod sursa (job #1085355) | Cod sursa (job #548428) | Cod sursa (job #467858) | Cod sursa (job #351682) | Cod sursa (job #434748)
Cod sursa(job #434748)
#include <stdio.h>
#include <stdlib.h>
#include <fstream>
using namespace std;
typedef struct {
int h;
int g;
}gutuie;
void merge(int starts,int startd,int stopd,gutuie *a){
int n=stopd-starts+1;
int is=starts,id=startd,stops=startd-1,it=0,i;
gutuie *temp=(gutuie*)malloc(n*sizeof(gutuie));
while(is<=stops && id<=stopd) {
if (a[is].h<a[id].h){
temp[it].h=a[is].h;
temp[it++].g=a[is++].g;
}
else if (a[is].h > a[id].h){
temp[it].h=a[id].h;
temp[it++].g=a[id++].g;
} else{ //egale
if (a[is].g < a[id].g){
temp[it].h=a[is].h;
temp[it++].g=a[is++].g;
}
else {
temp[it].h=a[id].h;
temp[it++].g=a[id++].g;
}
}
}
while (is<=stops){
temp[it].h=a[is].h;
temp[it++].g=a[is++].g;
}
while (id<=stopd){
temp[it].h=a[id].h;
temp[it++].g=a[id++].g;
}
for (i=0;i<n;i++){
a[starts+i].h=temp[i].h;
a[starts+i].g=temp[i].g;
}
free(temp);
}
void MS(int s,int d,gutuie *a){
if (s<d)
{
int m=(s+d)/2;
MS(s,m,a);
MS(m+1,d,a);
merge(s,m+1,d,a);
}
}
void MergeSort(int n,gutuie *a){
MS(0,n-1,a);
}
int pcmpa(int *v, int n){
int minim,p,c;
minim=v[0];p=0;
for (c=1;c<n;++c){
if (minim == 0) return p;
if (v[c]<minim){
minim=v[c];
p = c;
}
}
return p;
}
int main(){
int n,h,u,i,max=0,j,*best,*sbest,ch,k,niv=0,poz;
ifstream in("gutui.in");
ofstream out("gutui.out");
//ofstream test("test.txt");
in >> n; in >> h; in >> u;
gutuie *v=(gutuie*)calloc(n,sizeof(gutuie));
best=(int*)calloc(h/u+1,sizeof(int));
sbest=(int*)calloc(u,sizeof(int));
for (i=0;i<n;++i){
in >> v[i].h;
in >> v[i].g;
//total+=v[i].g;
}
MergeSort(n,v);
//test << "Se pot lua maxim "<<total<<"kg de gutui\n";
//test << "Gutuile sortate\n";
//for (i=n-1;i>=0;i--)
// test << "N=" << i<<":" <<v[i].h << " " << v[i].g << endl;
while (niv<=h/u){
k=0;
//test << "Acum incep cu niv=" << niv << endl;
max=0;
ch=0;
sbest=(int*)calloc(u,sizeof(int));
for (j=n-1;j>=0;--j){
//test << "testez daca v[" << j <<"].h=" << v[j].h<<" e in intervalul ("<<h-niv*u<<","<<h-(niv+1)*u+1<<endl;
if (v[j].h >= h-(niv+1)*u+1)
{
if (v[j].h <= h-niv*u)// dc e cuprins in nivelul curent
{
if (max<v[j].g) {
max=v[j].g;
if (best[niv]==0) best[niv]=max;
else{
sbest[ch++]=best[niv];
best[niv]=max;
}
}
else{
sbest[ch++]=v[j].g;
}
}
}
}
if (ch) poz=pcmpa(best,niv);//test<<"Cea mai proasta alegere e "<< best[poz]<<"pe poz="<<poz<<endl;}
for (i=0;i<ch && k<niv;i++){
if (sbest[i]>best[poz]){
best[poz]=sbest[i];
//test<<"Am gasit o imbunatatire si best["<<poz<<"]="<<best[poz]<<endl;
++k;
if (i!=ch-1) poz = pcmpa(best,niv);
}
}
//test << "La nivelul "<< niv <<" am best\n";
//for (i=0;i<=niv;i++)
// test << best[i] << " ";
//test << endl;
++niv;
}
max=best[0];
//printf("max=%d\n",max);
for (i=1;i<niv;i++) max+=best[i];//printf("max=%d\n",max);}
out << max;
free(v);
free(best);
free(sbest);
in.close();
out.close();
//test.close();
return 0;
}