Mai intai trebuie sa te autentifici.
Cod sursa(job #442024)
Utilizator | Data | 13 aprilie 2010 19:57:20 | |
---|---|---|---|
Problema | Gutui | Scor | 60 |
Compilator | c | Status | done |
Runda | teme_upb | Marime | 3.53 kb |
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define INF 1000000
void swap(int *x,int *y)
{
int temp;
temp = *x;
*x = *y;
*y = temp;
}
int choose_pivot(int i,int j )
{
return((i+j) /2);
}
void quicksort(int list[], int list2[],int m,int n)
{
int key,i,j,k;
if( m < n)
{
k = choose_pivot(m,n);
swap(&list[m],&list[k]);
swap(&list2[m],&list2[k]);
key = list[m];
i = m+1;
j = n;
while(i <= j)
{
while((i <= n) && (list[i] >= key))
i++;
while((j >= m) && (list[j] < key))
j--;
if( i < j)
{
swap(&list[i],&list[j]);
swap(&list2[i],&list2[j]);
}
}
// swap two elements
swap(&list[m],&list[j]);
swap(&list2[m],&list2[j]);
// recursively sort the lesser list
quicksort(list,list2,m,j-1);
quicksort(list,list2,j+1,n);
}
}
void printlist(int list[],int n)
{
int i;
for(i=0;i<n;i++)
printf("%i ",list[i]);
printf("\n");
}
/*
int max(int mat[][], int i, int j)
{
int l, m;
int max=-1;
for (l=0;l<i;l++)
for (m=0;m<j;m++)
if (mat[l][m]>max)
max = mat[l][m];
return max;
}*/
int main()
{
int N, H, U, i, j, k, max, maxx;
int* inaltime;
int* greutate;
int** best;
FILE* f;
FILE* g;
f= fopen("gutui.in","r");
fscanf(f, "%i %i %i\n", &N, &H, &U);
inaltime = (int*)calloc(N,sizeof(int*));
greutate = (int*)calloc(N,sizeof(int*));
best = (int**)calloc(N,sizeof(int*));
for (i=0; i<N; i++)
{
fscanf(f, "%i %i\n", &inaltime[i], &greutate[i]);
best[i] = (int*)calloc(N,sizeof(int));
}
// sortez descrescator dupa inaltime
quicksort(inaltime,greutate,0,N-1);
// print the result
//printf("The list after sorting using quicksort algorithm:\n");
// printlist(inaltime,N);
//printlist(greutate,N);
for (i=0;i<N;i++)
if (inaltime[i]<=H)
best[i][0] = greutate[i];
else
best[i][0] = -INF;
/*
for (i=0;i<N;i++)
{
for (j=0;j<N;j++)
printf("%i ",best[i][j]);
printf("\n");
}*/
for (i=0;i<N;i++)
for(k=1;k<N;k++)
{
if (inaltime[i]+k*U <= H)
{
max=0;
for(j=0;j<i;j++)
if (best[j][k-1]>max)
max=best[j][k-1];
//printf("max=%i\n",max);
best[i][k] = greutate[i] + max;
}
else best[i][k] = -INF;
}
//printf("----------------------------------\n");
maxx=0;
for (i=1;i<N;i++)
{
for (j=0;j<N;j++)
if (best[i][j]>maxx)
maxx=best[i][j];
//printf("%i ",best[i][j]);
//printf("\n");
}
g= fopen("gutui.out","w");
fprintf(g, "%i", maxx);
fclose(f);
fclose(g);
return 0;
/*
int pas;
int inc_interv, sf_interv;
pas = H;
int nr_intervale;
if ((H-inaltime[N-1]) % U != 0)
nr_intervale = ((H-inaltime[N-1]) / U )+1;
else
nr_intervale = (H-inaltime[N-1]) / U ;
a = (int*)malloc(nr_intervale*sizeof(int*));
int j;
for (i=0; i<nr_intervale; i++)
{
inc_interv = pas - U +1;
sf_interv = pas;
//printf ("inc_interv=%i\n",inc_interv);
//printf ("sf_interv=%i\n",sf_interv);
for (j=inc_interv;j<sf_interv;j++)
quicksort(greutate,inaltime,inc_interv,sf_interv);
printlist(inaltime,N);
printlist(greutate,N);
for (j=inc_interv;j<sf_interv;j++)
if (inaltime[j%10]==j)
printf("%i ", greutate[j]);
printf("\n");
a[i] = greutate[sf_interv%U];
printf("a[%i]=%i\n",i,a[i]);
int k=0;
int s=0;
while ((sf_interv -1 -k > inc_interv) && (k < i))
{
if (a[sf_interv-1-k] - a[k] > 0)
s+=a[sf_interv-1-k] - a[k];
else
break;
k++;
}
a[i]+=s;
pas = pas - U;
}
printlist(a,nr_intervale);
g= fopen("gutui.out","w");
fclose(f);
fclose(g);
return 0;
*/
}