Pagini recente » Cod sursa (job #61870) | Cod sursa (job #2940871) | Cod sursa (job #2844289) | Cod sursa (job #1926850) | Cod sursa (job #436465)
Cod sursa(job #436465)
#include <stdio.h>
#include <set>
#include <deque>
#include <algorithm>
using namespace std;
struct gutuie{
int h,w;
};
/*
bool operator < (const gutuie &x, const gutuie &y){
return x.h<
}
struct setcmp {
bool operator() (const gutuie x, const gutuie y) const{
return x.h<y.h;
}
};
*/
bool sortcmp (gutuie x, gutuie y){
return x.w>y.w;
}
/*
// intoarce cea mai mare pozitie cu h = pos
int at_end(deque<gutui> &l){
}
*/
#ifdef debug
#define P for(int i=0;i<l.size();i++){printf("(%d %d) , ", l[i].h, l[i].w);}printf("\b\b \b\b\n");
#else
#define P
#endif
void insert_in(deque<gutuie> &l, gutuie &x){
P
#ifdef debug
printf("(%d %d)\n",x.h, x.w);
#endif
if (l.size() == 0){
l.push_back(x);
P
return;
}
if (x.h < l.front().h){
l.push_front(x);
P
return;
}
if (x.h > l.back().h){
l.push_back(x);
P
return;
}
if (l.back().h == l.size()){
P
return;
}
if (x.h >= l.back().h){
l.push_back(x);
P
return;
}
int a=0, b=l.size(), m;
for(;;){
m=(a+b)/2;
if (x.h > m && l[m].h < x.h){
if (l[m+1].h >= x.h){
// insert
l.insert(l.begin()+m+1, x);
break;
}
}
if (a==m || b==m){
P;
break;
}
if (x.h < m || l[m].h > x.h)
b=m;
if (l[m].h < x.h)
a=m;
}
P
}
int main (){
int n,h,u,i,j,hm=0;
int gathered=0;
deque<gutuie> g, taken;
deque<gutuie>::iterator it;
//set<gutuie,setcmp> taken;
#ifndef debug
freopen("gutui.in","rt",stdin);
freopen("gutui.out","wt",stdout);
#endif
scanf("%d %d %d",&n,&h,&u);
#ifdef debug
printf("%d %d %d\n",n,h,u);
#endif
gutuie tmp;
// .h e folosit ca numar de pasi maxim dupa care se poate culege gutuia, nu ca inaltime efectiva
for (i=0; i<n; i++){
scanf("%d %d",&tmp.h, &tmp.w);
#ifdef debug
printf("(%d %d)\n",tmp.h, tmp.w);
#endif
tmp.h=((h-tmp.h)/u)+1;
#ifdef debug
printf("-(%d %d)\n",tmp.h, tmp.w);
#endif
if (tmp.h>hm)
hm=tmp.h;
g.push_back(tmp);
}
sort(g.begin(), g.end(), sortcmp);
#ifdef debug
for (i=0;i<g.size();i++){
printf("(%d %d) , ", g[i].h, g[i].w);
}
printf("\n");
printf("\n");
printf("\n");
#endif
/*
for (i=1;i<=g.size();i++){
if (g[i].h <= i){
gathered += g[i].w;
taken.insert(g[i]);
}else{
}
}
*/
for (it = g.begin(); it != g.end(); it++){
insert_in(taken, *it);
#ifdef debug
printf("\n");
#endif
}
for (it = taken.begin(); it != taken.end(); it++)
gathered += (*it).w;
printf("%d\n",gathered);
return 0;
}