Pagini recente » Cod sursa (job #440214) | Cod sursa (job #413676) | Cod sursa (job #1404102) | Cod sursa (job #2663682) | Cod sursa (job #440304)
Cod sursa(job #440304)
#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 t,unsigned long int &r){ //functie de adaugare in vector ordonat crescator
if(r==t) { //inserare initiala
a[t]=gr;
r++;
return;
}
if(gr<=a[t]) { //la inceput
for(int i=r;i>t;i--)
a[i]=a[i-1];
a[t]=gr;
r++;
return;
}
if(gr>=a[r-1]) { //la sfarsit
a[r]=gr;
r++;
return;
}
for(int i=t;i<r;i++) //inserare intre doua elemente
if(a[i]<=gr&&gr<=a[i+1]) {
for(int j=r;j>i+1;j--)
a[j]=a[j-1];
a[i+1]=gr;
r++;
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; // vector ce va fi ordonat si ajuta la calcularea greutatii optime
unsigned long int t=0,r=0; //t = index de inceput si r = sfarsit al vectorului ordonat
a=(unsigned long int *)malloc(n*sizeof(unsigned long int));
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++) //gutuile ce depasesc inaltimea maxima nu se pot lua O(n)
if(c[i][0]>h) {
c[i][0]=0;c[i][1]=0;
}
sorta2(c,n); //se sorteaza descrescator dupa inaltime O(n*log(n))
for(i=0;i<n;i++) //pt fiecare gutuie
if(k<=h-c[i][0]) { //se compara cu pasul curent pasul gutui h - inaltimea gutui
m=m+c[i][1]; // daca este mai mic se adauga la masa si in vectorul sortat
add(a,c[i][1],t,r);
k=k+u; //pasul curent creste cu u
}
else if(c[i][1]>a[t]) // daca gutuia nu se afla la pasul curent dar e mai grea decat minimul din vector
{
m=m-a[t]; //se elimina din vector si din suma minimul
t++;
m=m+c[i][1]; //se adauga in vector si suma greutatea noii gutui
add(a,c[i][1],t,r);
}
return m; //se returneaza masa
}
int main(){
unsigned long int c[100000][2]; //vectorul de gutui inaltimi/greutati
unsigned long int i,n,h,gr,u;
freopen("gutui.in", "r", stdin);
freopen("gutui.out", "w", stdout);
scanf("%ld",&n); //se citesc n ,h,u si gutuile cu greutatiile si inaltimile
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;
}