Pagini recente » Cod sursa (job #964180) | Cod sursa (job #1403870) | Cod sursa (job #1051102) | Cod sursa (job #3185213) | Cod sursa (job #439862)
Cod sursa(job #439862)
#include <stdio.h>
#define MAXN 100000
int N,Hmax, U;
int MaxTime;
int gre[MAXN]; // Tinem greutatile
int mom[MAXN]; // Ultimul moment in care se poate lua Gutui
int best[MAXN];
void Input(char* filename)
{
FILE *f = fopen(filename , "r");
fscanf(f, "%d%d%d", &N , &Hmax , &U);
for (int i = 0 ; i < N ; i++){
int h , g;
fscanf(f,"%d%d", &h , &g);
gre[i] = g;
mom[i] = (Hmax - h) / U ;
best[i] = 0; //initializam peste tot cu 0
}
fclose(f);
}
void swap(int* a , int* b)
{
int aux = *a;
*a = *b;
*b = aux;
}
int pivot(int p, int q)
{
int i,j, ii , jj;
i = p;
j = q;
ii = 0;
jj = -1;
while ( i < j )
{
if ( mom[i] > mom[j] )
{
swap(&mom[i], &mom[j]);
swap(&gre[i], &gre[j]);
ii = (ii - 1 ) * -1;
jj = (jj + 1) * -1;
}
i += ii;
j +=jj;
}
return i;
}
void quicksort(int p,int q)
{
int m;
if (p < q)
{
m = pivot(p, q);
quicksort(p, m - 1);
quicksort(m + 1, q);
}
}
void Sort()
{
for (int i = 0 ; i < N - 1; i++)
for (int j = i + 1 ; j < N ; j++)
if (mom[i] > mom[j])
{
swap(&mom[i] , &mom[j]);
swap(&gre[i] , &gre[j]);
}
}
// Returneaza pozitia valoarii minima gasita n best pe [0 , index]
int GetPos(int index)
{
int pos = index;
for (int i = index; i >= 0 ; i--)
{
if (best[pos] > best[i])
pos = i;
}
return pos;
}
void Solve()
{
for (int i = 0 ; i < N ; i++)
{
int pos = GetPos(mom[i]);
if (best[pos] < gre[i])
best[pos] = gre[i];
}
}
void Output(char *filename)
{
FILE *f = fopen("gutui.out", "w");
int sol = 0;
for (int i = 0 ; i < N ; i++)
sol += best[i];
fprintf(f,"%d", sol);
fclose(f);
}
int main(void)
{
Input("gutui.in");
quicksort(0 , N - 1);
/* for (int i = 0 ; i < N ; i++ )
printf("%d ", mom[i]);
*/
// Sort();
/*
puts("Moment");
for (int i = 0 ; i < N ; i++ )
printf("%d ", mom[i]);
puts("\nGreutate");
for (int i = 0 ; i < N ; i++ )
printf("%d ", gre[i]);
puts("");*/
Solve();
Output("gutui.out");
return 0;
}