Pagini recente » Cod sursa (job #738704) | Cod sursa (job #1369821) | Cod sursa (job #510730) | Cod sursa (job #3032936) | Cod sursa (job #437761)
Cod sursa(job #437761)
#include<stdio.h>
#include<stdlib.h>
#include<limits.h>
//#include<conio.h>
int n;
int N;
int H;
int U;
typedef struct Gutui {
int lvl;
int inaltime;
int greutate;
} Gutui;
struct Gutui g[100001];
void write(int x) {
FILE * g = fopen("gutui.out", "w");
fprintf(g, "%d", x);
}
void change( int *a, int *b ) {
int swap;
swap = *a;
*a = *b;
*b = swap;
}
void sort( int begin, int end ) {
int pivot, left, right;
if( end > begin + 1 ) {
pivot = g[begin].greutate;
left = begin + 1;
right = end;
while( left < right ) {
if(g[left].greutate <= pivot)
left ++;
else {
change(&g[left].greutate, &g[--right].greutate);
change(&g[left].inaltime, &g[--right].inaltime);
change(&g[left].lvl, &g[--right].lvl);
}
}
change(&g[--left].greutate, &g[begin].greutate);
change(&g[--left].inaltime, &g[begin].inaltime);
change(&g[--left].lvl, &g[begin].lvl);
}
}
/*
void sort() {
int i, j, aux, aux2;
for (i = 1; i <= N - 1; i++)
for (j = i + 1; j <= N; j++)
if (g[i].greutate < g[j].greutate) {
aux = g[i].greutate;
g[i].greutate = g[j].greutate;
g[j].greutate = aux;
aux = g[i].inaltime;
g[i].inaltime = g[j].inaltime;
g[j].inaltime = aux;
aux = g[i].lvl;
g[i].lvl = g[j].lvl;
g[j].lvl = aux;
}
}
*/
int find( int x, int v[], int nr ) {
int i, k = 0;
for( i = 1; i <= nr; i ++ )
if( x == v[i] ) k ++;
if( k != 0 ) return 1; // returneaza 1 daca x apare in v
return 0; // si 0, altfel
}
void gutui() {
int i, j, count[100001], suma = 0, nr = 0, k = 1, ok;
for( i = 1; i <= N; i ++ )
g[i].lvl = ( H - g[i].inaltime ) / U + 1 ;
sort(1, N);
// determina nivelul maxim
for( i = 1; i <= N ; i ++)
if( g[i].lvl > nr )
nr = g[i].lvl;
for( i = 1; i < nr; i ++ )
count[i] = 0;
for( i = 1; i <= N; i ++) {
ok = 0;
for( j = g[i].lvl; j >= 1; j -- )
if( ok != 1 )
if(find(j, count, k) != 1) {
count[k + 1] = j;
suma = suma + g[i].greutate;
ok = 1;
k = k + 1;
}
}
/* for (i = 1; i <= N; i++) {
printf("%d ", g[i].lvl);
printf("%d ", g[i].inaltime);
printf("%d", g[i].greutate);
printf("\n");
}
printf("%d ", suma);
*/
write(suma);
}
int main() {
FILE * f = fopen("gutui.in", "r");
int i;
fscanf(f, "%d", &N);
fscanf(f, "%d", &H);
fscanf(f, "%d", &U);
for (i = 1; i <= N; i++) {
fscanf(f, "%d", &g[i].inaltime);
fscanf(f, "%d", &g[i].greutate);
}
gutui();
return 0;
// getch();
}