Pagini recente » Cod sursa (job #2292442) | Cod sursa (job #2517437) | Cod sursa (job #437421) | Cod sursa (job #2084058) | Cod sursa (job #434860)
Cod sursa(job #434860)
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
long int N ;
int H , U;
typedef struct gutui
{
int h;
int g;
int nivel;
int luata;
} GUTUI;
GUTUI *G;
int maxim , indice;
void citire()
{
FILE *f = fopen ( "gutui.in" , "r" ) ;
fscanf( f , "%ld%d%d", &N , &H , &U) ;
G = ( GUTUI * ) malloc ( N * sizeof ( GUTUI ) ) ;
int i;
for ( i = 0 ; i < N ; i++ )
{
fscanf ( f , "%d%d" , &G[i].h , &G[i].g );
G[i].nivel = H / U - G[i].h / U;
}
fclose ( f );
}
int nr_niv;
int verifica()
{
int i;
for ( i = 0 ; i < N ; i++ )
if ( G[i].nivel != 0 ) return 1;
return 0;
}
void urmeaza ( int gre )
{
int i , j;
int *v = ( int * ) calloc ( N , sizeof ( int ) ) ;
int *s = ( int * ) calloc ( N , sizeof ( int ) ) ;
maxim = 0;
indice = 0;
for ( i = 0 ; i < N ; i++)
if ( ( G[i].nivel > 1 ) && ( G[i].g > gre) )
{
s[G[i].nivel]++;
if ( G[i].g > v[G[i].nivel] )
v[G[i].nivel] = G[i].g;
}
i =0;
int p = 0;
if (nr_niv > 2)
{
for ( i = 2 ; i <= nr_niv ; i++ )
if ( s[i] < i)
break;
}
else
if (s[2] >= 2)
i = 2;
else i =0;
for (j = 2 ; j < i+1 ; j++ )
if ( v[j] > maxim )
{
maxim = v[j];
p = j;
}
for ( i = 0 ; i < N ; i++)
if ( ( p == G[i].nivel) && ( maxim == G[i].g ) )
{
indice = i;
break;
}
free(v);
free(s);
}
void rezolva()
{
FILE *f = fopen ( "gutui.out" , "w" ) ;
int suma = 0;
int i , j , aux;
for ( i = 0 ; i < N ; i++)
for ( j = 0 ; j < N ; j++ )
{
if ( G[i].nivel < G[j].nivel )
{
aux = G[i].nivel;
G[i].nivel = G[j].nivel;
G[j].nivel = aux;
aux = G[i].h;
G[i].h = G[j].h;
G[j].h = aux;
aux = G[i].g;
G[i].g = G[j].g;
G[j].g = aux;
}
if ( G[i].nivel == G[j].nivel && G[i].g > G[j].g )
{
aux = G[i].nivel;
G[i].nivel = G[j].nivel;
G[j].nivel = aux;
aux = G[i].h;
G[i].h = G[j].h;
G[j].h = aux;
aux = G[i].g;
G[i].g = G[j].g;
G[j].g = aux;
}
}
nr_niv = 0;
for ( i = 0 ; i < N ; i++)
if ( G[i].nivel > nr_niv)
nr_niv = G[i].nivel;
while ( verifica() )
{
i = 0;
for ( i = 0; i < N ; i++)
if ( G[i].nivel > 0 )
break;
if (nr_niv > 1) urmeaza(G[i].g);
if ( maxim == 0 )
suma = suma + G[i].g;
else
{
suma = suma + maxim;
G[indice].nivel = 0;
}
for ( i = 0 ; i < N ; i++)
if ( G[i].nivel != 0 )
G[i].nivel --;
maxim = 0;
nr_niv --;
}
fprintf ( f , "%d\n" , suma );
fclose(f);
}
int main()
{
citire();
rezolva();
return 0;
}