Pagini recente » Cod sursa (job #2120092) | Cod sursa (job #1720785) | Cod sursa (job #832148) | Cod sursa (job #2392799) | Cod sursa (job #434710)
Cod sursa(job #434710)
# include <fstream>
# include <vector>
# include <algorithm>
# include <list>
# define MAXL 100000
using namespace std;
typedef struct gut{
int h;
int v;
int p;
}Gutuie;
bool compare(Gutuie a, Gutuie b){
//Gutuie *aa = (Gutuie*)a;
//Gutuie *bb = (Gutuie*)b;
if (a.p < b.p)
return false;
else
if (a.p > b.p)
return true;
else
if (a.v < b.v)
return true;
else
return false;
}
int main(){
int n, H, U, i, j, nsol, pas, s, k, l;
Gutuie x;
list <int> sol;
list <int>::iterator it;
vector <Gutuie> g;
fstream fin, fout;
fin.open("gutui.in",ios::in);
fout.open("gutui.out",ios::out);
fin>>n>>H>>U;
for (i=0;i<n;i++){
//fscanf(fin,"%d%d",&g[i].h,&g[i].v);
fin>>x.h>>x.v;
x.p = (H - x.h)/U + 1;
g.push_back(x);
}
sort(g.begin(), g.end(), compare);
nsol = 0;
for (i=0;i<n;i++){
if (i==0 || g[i].p != g[i-1].p){ //pasul urmator;
pas = g[i].p;
for (j=i;j<n && g[j].p == pas && j-i<pas;j++){//parcurg gutuile de la pasul curent(sunt in ordine descrescatoare;
if (nsol<pas){
//inserez pe g[j].v in vectorul sol a.i. sa ramana sortat descrescator;
//for (k=0;k<nsol;k++)
for (it = sol.begin(), k=0;k<nsol;++k,++it)
if (*it<g[j].v)
break;
sol.insert(it,g[j].v);
nsol++;
}
else{
if (g[j].v > sol.back()){
//elimin ultimul element din sol si inserez pe g[j].v;
for (k=0, it = sol.begin();k<nsol;++k, ++it)
if (*it<g[j].v)
break;
//for (l=nsol;l>k;l--)
// sol[l] = sol[l-1];
//sol[l] = g[j].v;
sol.insert(it,g[j].v);
}
}
}
}
}
s = 0;
for (it = sol.begin();it!=sol.end();++it)
s+=*it;
//fprintf(fout,"%d\n",s);
fout<<s<<"\n";
fin.close();
fout.close();
return 0;
}