Pagini recente » Cod sursa (job #2832069) | Cod sursa (job #2436858) | Cod sursa (job #58048) | Cod sursa (job #2259626) | Cod sursa (job #463590)
Cod sursa(job #463590)
#include<fstream>
#include<vector>
#include<algorithm>
using namespace std;
//structura unei gutui
struct Gutui{
long h; //inaltime
long w; //greutate
int mark; //culeasa sau nu
bool operator() (Gutui a, Gutui b) { if (a.h==b.h) return (a.w<b.w); return (a.h<b.h); } //functie de comparare dupa inaltime si greutate in cazul in care inaltimile sunt egale
}gutui;
bool weigthcompare (Gutui a, Gutui b) { return (a.w < b.w);} //functie de comparare dupa greutate
int main(){
long n,h,u,u1=0,umax=0;
ifstream fin ("gutui.in");
ofstream fout ("gutui.out");
fin>>n>>h>>u;
Gutui max;
vector<Gutui> g(n);
for (long i=0; i<n; i++)
fin>>g[i].h>>g[i].w;
for (long i=0; i<n; i++)
{
g[i].mark=0;
}
//sortare crescatoare dupa inaltimi
sort(g.begin(),g.end(),gutui);
//inversarea vectorului
Gutui aux;
for (long i=0; i<n/2; i++)
{
aux=g[i];
g[i]=g[n-i-1];
g[n-i-1]=aux;
}
long i=0;
while (i<n)
{
//verificam daca gutuia se poate culege
if (g[i].h+u1 < h && g[i].mark == 0)
{
//marim pasul si verificam daca urmatorul pas va fi ultimul in care gutuia i va putea fi culeasa
u1+=u;
if (g[i].h+u1 == h)
{
umax+=g[i].w;
g[i].mark=1;
i++;
}
//daca nu, atunci gasim gutuia cu greutate maxima si o culegem
else
{
max= *max_element(g.begin()+i,g.end(),weigthcompare);
for (long j=i; j<n; j++)
if (g[j].w==max.w && g[j].mark==0)
{
umax+=g[j].w;
g[j].mark=1;
}
}
}
else
//in cazul in care se depaseste h se marcheaza gutuia si se trece la urmatorul pas
{
g[i].mark=1;
i++;
}
}
//afisare si inchidere de fisiere
fout<<umax<<endl;
fin.close();
fout.close();
return 0;
}