Pagini recente » Cod sursa (job #1985714) | Cod sursa (job #784850) | Clasament | Cod sursa (job #2704843) | Cod sursa (job #427851)
Cod sursa(job #427851)
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
int partition(vector<int> &a, vector<int> &b, int p, int r)
{
int i, j, x;
x = a[r];
i = p - 1;
for(j = p; j < r; j++)
if(a[j] >= x)
{
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(vector<int> &a, vector<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 i, j, hh, ww, maxim = 0;
vector<int> weight, height, NrGutui, Sol;
vector<int>::iterator it;
ifstream in("gutui.in");
ofstream out("gutui.out");
in >> n;
in >> h;
in >> u;
for(i = 0; i < n; i++)
{
in >> hh; height.push_back(hh);
in >> ww; weight.push_back(ww);
}
// sortat descrescator dupa inaltime
quicksort(height, weight, 0, n - 1);
for(i = 0; i < n; i++)
{
Sol.push_back(weight[i]);
NrGutui.push_back(1);
for(j = 0; j < i; j++)
if( ( (height[i] + NrGutui[j] * u) <= h) && (Sol[i] <= Sol[j] + weight[i]) )
{
Sol[i] = Sol[j] + weight[i];
NrGutui[i] = NrGutui[j] + 1;
}
if(Sol[i] > maxim)
maxim = Sol[i];
}
out << maxim;
in.close();
out.close();
return 0;
}