Cod sursa(job #434834)

Utilizator razielRazvan Madalin Oita raziel Data 6 aprilie 2010 17:04:43
Problema Gutui Scor 10
Compilator cpp Status done
Runda teme_upb Marime 1.76 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) + 1;
    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++) {
        if (best[i - 1][aux] <= h)
            aux--;
        for (int j = 0; j <= aux; 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;
    for (int i = 0; i < dim; i++) {
        sw = 0;
        while (best[i][j] != 0 && j < n && !sw) {
            if (best[i][j] > h) {
                gmax += gutui[j - 1].weight;
                sw = 1;
            }
            j++;
        }
        if (!sw)
            gmax += gutui[j - 1].weight;
        j = 0;
    }

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

    return 0;
}