Cod sursa(job #435031)

Utilizator razielRazvan Madalin Oita raziel Data 6 aprilie 2010 20:19:31
Problema Gutui Scor 0
Compilator cpp Status done
Runda teme_upb Marime 4.01 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <cstdlib>
using namespace std;

struct gutuie {
    unsigned int height;
    unsigned int weight;
};

bool operator < (gutuie a, gutuie b) {
    return a.height < b.height;
}

int main() {
    unsigned int n, h, u, dim;
    gutuie g;
    vector<gutuie> gutui;
    unsigned int** best;
    unsigned int gmax;

    ifstream fin("gutui.in");
    fin >> n >> h >> u;
    for (int i = 0; i < n; i++) {
        fin >> g.height >> g.weight;
        gutui.push_back(g);
    }
    fin.close();

    sort(gutui.begin(), gutui.end());

    dim = ((h - gutui[0].height) / u) + 2;
    best = (unsigned int**)calloc(dim + 1, sizeof(unsigned int*));
    for (int i = 0; i < dim; i++)
        best[i] = (unsigned int*)calloc(n + 1, sizeof(unsigned int));

    int aux = n - 1;
    for (int j = 0; j < n; j++)
        best[0][j] = gutui[j].height;
    for (int i = 1; i < dim; i++) {
        for (int j = 0; j < n; j++)
            best[i][j] = u + best[i - 1][j];
    }

    /*for (int i = 0; i < dim; i++) {
        for (int j = 0; j < n; j++)
            cout << best[i][j] << " ";
        cout << endl;
    }
    cout << endl;*/

    gmax = 0;
    int j = 0;
    int sw = 0;
    aux = n;
    int nrp = 0;
    int max;
    int poz;
    int poz2;
    for (int i = 0; i < dim - 1; i++) {
        nrp = 0;
        for (j = 0; j < aux; j++) {
            if (best[i + 1][j] > h)
                nrp++;
        }
        if (nrp == 0) {
            max = 0;
            poz = 0;
            for (j = 0; j < aux; j++)
                if (gutui[j].weight >= max)
                    max = gutui[j].weight;
            for (j = 0; j < aux; j++)
                if (gutui[j].weight == max)
                    poz = j;
            gmax += gutui[poz].weight;
            best[i][poz] = 0;
            best[i + 1][poz] = 0;
            gutui[poz].weight = 0;
            gutui[poz].height = 0;
        }
        else {
            max = 0;
            poz = 0;
            poz2 = 0;
            for (j = 0; j < aux; j++) {
                if (best[i + 1][j] > h) {
                    poz2 = j;
                    break;
                }
            }
            sw = 0;
            for (j = poz2; j < aux; j++) {
                if (best[i][j] != 0)
                    sw = 1;
            }
            if (!sw) {
                aux = poz2;
                for (j = 0; j < aux; j++)
                if (gutui[j].weight >= max)
                    max = gutui[j].weight;
                for (j = 0; j < aux; j++)
                    if (gutui[j].weight == max)
                        poz = j;
                gmax += gutui[poz].weight;
                best[i][poz] = 0;
                best[i + 1][poz] = 0;
                gutui[poz].weight = 0;
                gutui[poz].height = 0;
            }
            else {
                for (j = poz2; j < aux; j++) {
                    if (gutui[j].weight >= max)
                        max = gutui[j].weight;
                }
                for (j = 0; j < aux; j++)
                    if (gutui[j].weight == max)
                        poz = j;
                gmax += gutui[poz].weight;
                best[i][poz] = 0;
                best[i + 1][poz] = 0;
                gutui[poz].weight = 0;
                gutui[poz].height = 0;
                aux = poz2;
            }
        }
    }
    /*for (int i = 0; i < dim; i++) {
        if (aux == 0)
            break;
        sw = 0;
        while (best[i][j] != 0 && j < aux && !sw) {
            if (best[i][j] > h) {
                gmax += gutui[j - 1].weight;
                aux = j - 1;
                sw = 1;
            }
            j++;
        }
        if (!sw) {
            gmax += gutui[j - 1].weight;
            aux = j - 1;
        }
        j = 0;
    }*/

    ofstream fout("gutui.out");
    fout << gmax << endl;
    fout.close();

    return 0;
}