Pagini recente » Cod sursa (job #2941798) | Cod sursa (job #1147654) | Cod sursa (job #36337) | Cod sursa (job #813435) | Cod sursa (job #434904)
Cod sursa(job #434904)
#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;
aux = n;
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;
}