Pagini recente » Cod sursa (job #2318572) | Cod sursa (job #440265)
Cod sursa(job #440265)
#include <stdio.h>
#include <stdlib.h>
int sort1(const void *x, const void *y) { //functie de comparare pt sortare
return (*(int*)y - *(int*)x); //sortare descrescatoare
}
void sorta2(unsigned long int a[][2],unsigned long int n){ // apelare qsort pt a
qsort(a,n,sizeof(unsigned long int[2]),sort1);
}
void add (unsigned long int a[],unsigned long int gr,unsigned long int in,unsigned long int &sf){ //functie de adaugare in vector ordonat crescator
if(sf==in) { //inserare initiala
a[in]=gr;
sf++;
return;
}
if(gr<=a[sf]) { //la inceput
for(int i=sf;i>in;i--)
a[i]=a[i-1];
a[in]=gr;
sf++;
return;
}
if(gr>=a[sf-1]) { //la sfarsit
a[sf]=gr;
sf++;
return;
}
for(int i=in;i<sf;i++) //inserare intre doua elemente
if(a[i]<=gr&&gr<=a[i+1]) {
for(int j=sf;j>i+1;j--)
a[j]=a[j-1];
a[i+1]=gr;
sf++;
return;
}
}
unsigned long int gutui(unsigned long int c[][2],unsigned long int n,unsigned long int h,unsigned long int u){ //functia care calculeaza greutatea optima
unsigned long int i,k=0,m=0; //i index , k pasul la care ne aflam pe inaltime , m masa
unsigned long int a[n]; // vector ce va fi ordonat si ajuta la calcularea greutatii optime
unsigned long int sf=0,in=0; //index de inceput si sfarsit al vectorului ordonat
if(u>=h) {
for(i=0;i<n;i++)
if(m<c[i][1]&&c[i][0]<=h) // daca se poate lua un singura gutuie o luam pe cea maxima si iesim
m=c[i][1];
return m; }
for(i=0;i<n;i++)
if(c[i][0]>h) {c[i][0]=0;c[i][1]=0;}
sorta2(c,n);
for(i=0;i<n;i++)
if(k<=h-c[i][0]) {
m=m+c[i][1];
add(a,c[i][1],in,sf);
k=k+u;
}
else if(c[i][1]>a[in])
{
m=m-a[in];
in++;
m=m+c[i][1];
add(a,c[i][1],in,sf);
}
return m;
}
int main(){
unsigned long int c[100000][2];
unsigned long int i,n,h,gr,j,u,a1,a2;
freopen("gutui.in", "r", stdin);
freopen("gutui.out", "w", stdout);
scanf("%ld",&n);
scanf("%ld",&h);
scanf("%ld",&u);
for (i=0;i<n;i++) {
scanf("%ld",&c[i][0]);
scanf("%ld",&c[i][1]);
}
gr=gutui(c,n,h,u);
printf("%ld\n",gr);
return 0;
}