Cod sursa(job #442628)

Utilizator escu.victorPopescu Victor escu.victor Data 14 aprilie 2010 21:27:01
Problema Gutui Scor 70
Compilator cpp Status done
Runda teme_upb Marime 2.77 kb
#include <fstream>
#include <iostream>
#include <vector>
#include <algorithm>
#include <stdlib.h>
#define INF 100000
using namespace std;

int partition(int *a, int *b, int p, int r)
{
    int i, j, x, y;
    x = a[r];
    y = b[r];
    i = p - 1;
    for(j = p; j < r; j++)
        if((a[j] > x) || (a[j] == x && b[j] > y))
        {
            i++;
            swap(a[i], a[j]);
            swap(b[i], b[j]);
        }
    swap(a[i+1], a[r]);
    swap(b[i+1], b[r]);   
    return (i + 1);   
}   

void quicksort(int *a,int *b, int p, int r)
{
    if(p < r)
    {
        int q = partition(a, b, p, r);
        quicksort(a, b, p, q - 1);
        quicksort(a, b, q + 1, r);
    }
}       

int main()
{
    int n, h, u;    // nr. gutui, inaltime maxima, cu cat se ridica
    int nn, hh, ww;
    int i, j, min, poz, maxim = -INF;
    int *weight, *height, *NrGutui, *Sol, *renunt;
   
    ifstream in("gutui.in");       
    ofstream out("gutui.out");
    in >> nn;
    in >> h;
    in >> u;
   
    weight = (int *)malloc(nn * sizeof(int));
    height = (int *)malloc(nn * sizeof(int));
    renunt = (int *)malloc(nn * sizeof(int));
    n = 0;
    for(i = 0; i < nn; i++)
    {
        in >> hh;        in >> ww;   
        if(hh <= h)
        {
            height[n] = hh;
            weight[n] = ww;
            renunt[n] = 0;
            n++;
        }   
    }
   
    // sortat descrescator dupa inaltime
    quicksort(height, weight, 0, n - 1);
   
    Sol = (int *)malloc(n * sizeof(int));
    NrGutui = (int*)malloc(n * sizeof(int));
   

    Sol[0] = weight[0];
    NrGutui[0] = 1;
   
    for(i = 1; i < n; i++)
    {
        //    cout<<height[i] + NrGutui[i - 1] * u<<" ";
        if((height[i] + NrGutui[i - 1] * u) <= h)
        {
            Sol[i] = Sol[i - 1] + weight[i];
            NrGutui[i] = NrGutui[i - 1] + 1;
        }
        else
        {
            // Nu poti sa culegi gutuia i
            NrGutui[i] = NrGutui[i - 1];
            Sol[i] = Sol[i - 1];
            min = INF;
            poz = 0;
           
            // Incerci sa renunti la una culeasa, astfel incat daca ai renunta la ea
            // si ai culege gutuia i, ai avea un profit mai mare
            for(j = 0; j < i; j++)
                if((renunt[j] == 0) && (min > weight[j]))
                {
                    min = weight[j];
                    poz = j;
                }
               
            if(min < weight[i])
            {
                renunt[poz] = 1;
                Sol[i] = Sol[i - 1] - weight[poz] + weight[i];
            }
            else
                renunt[i] = 1;
        }
        //cout<<Sol[i]<<" "<<NrGutui[i]<<"\n" ;
    }   
               
    out<<Sol[n - 1];               
               
    in.close();
    out.close();
    return 0;
}