Pagini recente » Cod sursa (job #881694) | Cod sursa (job #420629) | Cod sursa (job #2342016) | Cod sursa (job #198667) | Cod sursa (job #427091)
Cod sursa(job #427091)
#include <stdio.h>
int *hh,*gg,*pus;
int n,h,u,crt;
#define CRESC 10
//functie de sortare dupa inaltime=> tb inlocuita ca sa fie in nlogn
//tb un quicksort
void sort()
{
int i,j,t;
for(i=0;i<n-1;i++)
for (j=i+1;j<n;j++)
if (hh[i]>hh[j]) {t=hh[i];hh[i]=hh[j];hh[j]=t;
t=gg[i];gg[i]=gg[j];gg[j]=t; }
}
//cauta maximul dupa pasi
int maxim(int pasi)
{
int ok=0,max=-1,poz=-1,i;
for (i=crt;i>=0;i--)
//daca se poate lua
if (!pus[i] && (hh[i]+u*pasi)<=h)
{
ok=1;
//am ajuns la primul care se poate lua dupa inca 2 pasi
//pana aici i-am parcurs pe cei care se pot lua doar dupa 1 pas
if (hh[i]+u*(pasi+1)<=h) break;
else
//caut maximul intre cei care se pot lua doar dupa 1 pas
if (gg[i]>max) {max=gg[i];poz=i;}
}
//nu am gasit nici unul
if (!ok) return -1;
if (poz==-1) poz=i;
crt=i;
pus[poz]=1;return gg[poz];
}
int main()
{
int i;
FILE *fis=fopen("gutui.in","r");
fscanf(fis,"%d%d%d",&n,&h,&u);
hh=(int*)malloc(n*sizeof(int));
gg=(int*)malloc(n*sizeof(int));
pus=(int*)malloc(n*sizeof(int));
for(i=0;i<n;i++)
{fscanf(fis,"%d%d",&hh[i],&gg[i]);pus[i]=0;}
fclose(fis);
sort();
int pasi=0;
int gr=0;
int tmp;
crt=n-1;
//crt e ultima pozitie la care am ajuns
while(1)
{
tmp=maxim(pasi);
if (tmp<0) break;
gr+=tmp;
pasi++;
}
FILE *fis1=fopen("gutui.out","w");
fprintf(fis1,"%d\n",gr);
fclose(fis1);
return 0;
}