Pagini recente » Cod sursa (job #1100818) | Cod sursa (job #596657) | Cod sursa (job #807660) | Cod sursa (job #1107009) | Cod sursa (job #434747)
Cod sursa(job #434747)
#include <fstream>
#include <iostream>
#include <vector>
#include <algorithm>
#include <stdlib.h>
#define INF 100000
using namespace std;
int partition(int *a, int *b, int p, int r)
{
int i, j, x, y;
x = a[r];
y = b[r];
i = p - 1;
for(j = p; j < r; j++)
if((a[j] > x) || (a[j] == x && b[j] > y))
{
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(int *a,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 nn, hh, ww;
int i, j, min, poz, maxim = -INF;
int *weight, *height, *NrGutui, *Sol, *renunt;
ifstream in("gutui.in");
ofstream out("gutui.out");
in >> nn;
in >> h;
in >> u;
weight = (int *)malloc(nn * sizeof(int));
height = (int *)malloc(nn * sizeof(int));
renunt = (int *)malloc(nn * sizeof(int));
n = 0;
for(i = 0; i < nn; i++)
{
in >> hh; in >> ww;
if(hh <= h)
{
height[n] = hh;
weight[n] = ww;
renunt[n] = 0;
n++;
}
}
// sortat descrescator dupa inaltime
quicksort(height, weight, 0, n - 1);
/*
for(i = 0; i < n; i++)
cout<< height[i]<<" "<<weight[i]<<"\n";
Sol = (int *)malloc(n * sizeof(int));
NrGutui = (int*)malloc(n * sizeof(int));
Sol[0] = weight[0];
NrGutui[0] = 1;
for(i = 1; i < n; i++)
{
// cout<<height[i] + NrGutui[i - 1] * u<<" ";
if((height[i] + NrGutui[i - 1] * u) <= h)
{
Sol[i] = Sol[i - 1] + weight[i];
NrGutui[i] = NrGutui[i - 1] + 1;
}
else
{
// Nu poti sa culegi gutuia i
NrGutui[i] = NrGutui[i - 1];
Sol[i] = Sol[i - 1];
min = INF;
poz = 0;
// Incerci sa renunti la una culeasa, astfel incat daca ai renunta la ea
// si ai culege gutuia i, ai avea un profit mai mare
for(j = 0; j < i; j++)
if((renunt[j] == 0) && (min > weight[j]))
{
min = weight[j];
poz = j;
}
if(min < weight[i])
{
renunt[poz] = 1;
Sol[i] = Sol[i - 1] - weight[poz] + weight[i];
}
else
renunt[i] = 1;
}
//cout<<Sol[i]<<" "<<NrGutui[i]<<"\n" ;
}
*/
out<<Sol[n - 1];
in.close();
out.close();
return 0;
}