Pagini recente » Cod sursa (job #2332125) | Cod sursa (job #805709) | Cod sursa (job #1398510) | Cod sursa (job #443502) | Cod sursa (job #440436)
Cod sursa(job #440436)
#include <stdio.h>
#include <stdlib.h>
typedef unsigned long long int uint64_t;
typedef struct gutui {
uint64_t h,g;
int cules;
} Gutui;
int compare(const void* a, const void* b){
return (((Gutui*)b)->h-((Gutui*)a)->h);
}
int compare2(const void* a, const void* b){
return (((Gutui*)b)->g-((Gutui*)a)->g);
}
int compar2(const void* a, const void* b){
return (*((uint64_t*)a)-*((uint64_t*)b));
}
int main() {
FILE *fi=fopen("gutui.in","r");
FILE *fo=fopen("gutui.out","w");
Gutui *g;
uint64_t n,i,j,total=0,h,u,*q,ales,k=0,k2=0;
fscanf(fi,"%llu %llu %llu",&n,&h,&u);
g=(Gutui*)calloc(n,sizeof(Gutui));
q=(uint64_t*)calloc(n,sizeof(uint64_t));
for (i=0;i<n;i++) {
fscanf(fi,"%llu %llu",&g[i].h,&g[i].g);
}
qsort(g,n,sizeof(Gutui),compare);
for (i=0;i<n;i++)
fprintf(fo,"%llu\t%llu\n",g[i].h,g[i].g);
for (i=0;i<n;i++) {
ales=i;
if (g[i].h<=h) {
h-=u;
for (j=i+1;j<n;j++) {
if (g[j].h>h) {
if (g[j].g>g[ales].g)
ales=j;
}
else break;
}
g[ales].cules=1;
q[k++]=g[ales].g;
}
}
//dupa ce a ales incearca sa maximizeze suma
//sortez crescator dupa greutate
qsort(q,k,sizeof(uint64_t),compar2);
//sortez descrescator dupa greutate
qsort(g,n,sizeof(Gutui),compare2);
for (i=0;i<n;i++)
if (!g[i].cules)
q[k2++]=g[i].g;
for (i=0;i<k;i++)
total+=q[i];
fprintf(fo,"%llu",total);
fclose(fi);
fclose(fo);
return 0;
}