Pagini recente » Cod sursa (job #2316040) | Cod sursa (job #3141844) | Cod sursa (job #861618) | Cod sursa (job #2057658) | Cod sursa (job #435031)
Cod sursa(job #435031)
#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;
}