Pagini recente » Istoria paginii runda/343242354534/clasament | Istoria paginii runda/concurs_27mai/clasament | Istoria paginii runda/usu10mii/clasament | Cod sursa (job #357107) | Cod sursa (job #438108)
Cod sursa(job #438108)
#include<stdio.h>
#include<stdlib.h>
#include<limits.h>
//#include<conio.h>
int n;
int N;
int H;
int U;
int count[100003];
int lvl[100003];
int inaltime[100003];
int greutate[100003];
void write(int x) {
FILE * g = fopen("gutui.out", "w");
fprintf(g, "%d", x);
}
int partition(int l, int r) {
int pivot, i, j, t;
pivot = greutate[l];
i = l;
j = r + 1;
while(1) {
do i ++; while( greutate[i] <= pivot && i <= r );
do j --; while( greutate[j] > pivot );
if( i >= j ) break;
t = greutate[i];
greutate[i] = greutate[j];
greutate[j] = t;
t = inaltime[i];
inaltime[i] = inaltime[j];
inaltime[j] = t;
// t = lvl[i];
// lvl[i] = lvl[j];
// lvl[j] = t;
}
t = greutate[l];
greutate[l] = greutate[j];
greutate[j] = t;
t = inaltime[l];
inaltime[l] = inaltime[j];
inaltime[j] = t;
// t = lvl[l];
// lvl[l] = lvl[j];
// lvl[j] = t;
return j;
}
/* int partition2(int l, int r) {
int pivot, i, j, t;
pivot = ( H - inaltime[i] ) / U + 1;
i = l;
j = r + 1;
while(1) {
do i ++; while( ( H - inaltime[i] ) / U + 1 <= pivot && i <= r );
do j --; while( ( H - inaltime[i] ) / U + 1 > pivot );
if( i >= j ) break;
t = greutate[i];
greutate[i] = greutate[j];
greutate[j] = t;
t = inaltime[i];
inaltime[i] = inaltime[j];
inaltime[j] = t;
// t = lvl[i];
// lvl[i] = lvl[j];
// lvl[j] = t;
}
t = greutate[l];
greutate[l] = greutate[j];
greutate[j] = t;
t = inaltime[l];
inaltime[l] = inaltime[j];
inaltime[j] = t;
// t = lvl[l];
// lvl[l] = lvl[j];
// lvl[j] = t;
return j;
}
*/
void sort( int l, int r ) {
int j;
if( l < r ) {
j = partition( l, r );
sort( l, j - 1);
sort( j + 1, r );
}
}
/*
void sort2( int l, int r ) {
int j;
if( l < r ) {
j = partition( l, r );
sort2( l, j - 1);
sort2( j + 1, r );
}
}*/
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, suma = 0, nr = 0, k = 1, ok, nivel, max = 0;
for( i = 1; i <= N; i ++ )
if( (H - inaltime[i]) / U + 1 > max ) max = (H - inaltime[i]) / U + 1;
//lvl[i] = ( H - inaltime[i] ) / U + 1 ;
for( i = 1; i <= max; i ++ )
count[i] = i;
sort(1, N);
for( i = N; i >= 1; i --) {
if(max > 0) {
nivel = ( H - inaltime[i] ) / U + 1;
if(nivel == count[nivel] ) {
suma = suma + greutate[i];
while( nivel < max ) {
count[nivel] = count[nivel + 1];
nivel = nivel + 1;
}
max = max - 1;
}
else {
suma = suma + greutate[ i ];
while( nivel < max ) {
count[nivel - ( N - i )] = count[nivel - ( N - i ) + 1];
nivel = nivel + 1;
}
max = max - 1;
}
}
}
/* for (i = 1; i <= N; i++) {
printf("%d ", inaltime[i]);
printf("%d", greutate[i]);
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", &inaltime[i]);
fscanf(f, "%d", &greutate[i]);
}
gutui();
return 0;
// getch();
}