Cod sursa(job #1201601)

Utilizator devilz05Orzan Alexandru devilz05 Data 25 iunie 2014 15:10:10
Problema Gutui Scor 0
Compilator c Status done
Runda teme_upb Marime 2.08 kb
#include <stdio.h>

int *openFile(char *fileName, int *h, int *w, int *N, int *H, int *U)
{
    FILE *file = NULL;
    int i;
    
    file = fopen(fileName, "r+");
    if (file == NULL)
    {
        printf("%s does not exist.\n", fileName);
        return 0;
    }
    
    fscanf(file, "%i%i%i", N, H, U);
    for (i=0; i<*N; ++i)
    {
        fscanf(file, "%i", &h[i]);
        fscanf(file, "%i", &w[i]);
    }
    
    fclose(file);
    
    return 1;
}

int fileWrite(char *fileName, int max)
{
    FILE *file = NULL;
    
    file = fopen(fileName, "w+");
    if (file == NULL)
    {
        printf("Could not create file.\n");
        return 0;
    }
    
    fprintf(file, "%i", max);
    
    fclose(file);
    return 1;
}

void swap(int i, int j, int *h, int *w)
{
    int aux = h[i];
    h[i] = h[j];
    h[j] = aux;
    aux = w[i];
    w[i] = w[j];
    w[j] = aux;
}
 
int partition(int left, int right, int *h, int *w)
{
    
    int i, j, x = h[left];
    i = left;
    for(j = left + 1; j <= right; j++)
        if(h[j] > x)
        {
            i = i + 1;
            swap(i, j, h, w);
        }        
    swap(left, i, h, w);
    return i;
}
 
void qsort(int left, int right, int *h, int *w)
{
    int pos;
    if(left >= right)
        return;
    pos = partition(left, right, h, w);
    qsort(left, pos - 1, h, w);
    qsort(pos + 1, right, h, w);
}

int min(int a, int b)
{
    return a>b?b:a;
}

int main()
{
    int N, H, U;
    int x, max, t[100000]={0};
    int w[100000]={0}, h[100000]={0};
    int i, j;
    
    openFile("gutui.in", h, w, &N, &H, &U);
    
    qsort(0, N, h, w);
    
    t[1] = w[0];
    max = w[0];
    
    for(i = 1; i < N; ++i)
    {
        x = (H - h[i]) / U;
        for(j = min(i, x) + 1; j >= 1; --j)
        {
            if(t[j - 1] + w[i] > t[j])
            {
                t[j] = t[j - 1] + w[i];
                if(t[j] > max)
                    max = t[j];
            }
        }
    }
    
    fileWrite("gutui.out", max);
    
    return 0;
}