Pagini recente » Cod sursa (job #1025212) | Cod sursa (job #2621514) | Cod sursa (job #1556315) | Cod sursa (job #1899755) | Cod sursa (job #2428755)
#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
#include <algorithm>
#include <cstring>
class input_parser{
protected:
FILE *fin;///Input file
static const int max_load=1<<10;///Maximum Allocation
size_t pos;///Index of the buffer
char buffer[max_load];///Input is being store here
public:
input_parser():pos(0){}
input_parser(const char *);///Opens the specified file
void open(const char *);///^
template<class T>
void read(T &);///Read function
void read(){}
template<class T,typename ... Args>
void read(T & ,Args&...args);
void read(char *,size_t);///Read a string
inline char next();///Advances the buffer
};
input_parser::input_parser(const char * fName){
this->fin=fopen(fName,"r");
this->pos=0;
}
void input_parser::open(const char *fName){
delete this->fin;
memset(this->buffer,0,sizeof(this->buffer));
this->fin=fopen(fName,"r");
this->pos=0;
}
inline char input_parser::next(){
if(this->pos==max_load)
fread(this->buffer,1,max_load,this->fin),this->pos=0;
return this->buffer[this->pos++];
}
template<class T>
void input_parser::read(T & nr){
char c;
int semn=1;
nr=0;
c=this->next();
while(!isdigit(c) && c!='-')
c=this->next();
while(c=='-')
c=this->next(),semn*=-1;
while(isdigit(c))
nr=nr*10+c-'0',c=this->next();
nr*=semn;
}
template<class T,typename ... Args>
void input_parser::read(T & t,Args&...args){
read(t);
read(args...);
}
void input_parser::read(char *chp,size_t sz){
char c;
c=next();
while(c==' ' || c=='\n')
c=next();
for(size_t i=0;i<sz && c!=' ' && c!='\n';i++)
chp[i]=c,c=next();
}
input_parser in("lupu.in");
struct oaie{
int d,l;
bool operator < (const oaie & aux)const{
return d>aux.d;
}
}auxx;
long long suma=0;
std::ofstream out("lupu.out");
std::vector<oaie>v;
std::priority_queue<int,std::vector<int>,std::greater<int> > pq,pq2;
int main(){
int n,x,l;
bool ok=1;
in.read(n,x,l);
v.reserve(n+1);
for( register int i=1;i<=n;i++)
in.read(auxx.d,auxx.l),v.push_back(auxx);
std::sort(v.begin(),v.end());
for(register int i=0;i<n;i++){
if(v[i].d+suma<=x)
suma+=l,pq.push(v[i].l),pq2.push(v[i].l);
else{
int cnt=0,last=0;
if(ok)
pq2=pq;
ok=1;
long long sumad=0;
while(!pq2.empty() && v[i].d+suma-cnt*l>x )
sumad+=pq2.top(),pq2.pop(),cnt++;
if(cnt>0 && sumad<=v[i].l &&v[i].d+suma-cnt*l<=x){
suma-=cnt*l;
for(int j=1;j<=cnt;j++)
pq.pop();
pq.push(v[i].l);
suma+=l;
ok=0;
pq2.push(v[i].l);
}
}
}
long long sumax=0;
while(!pq.empty())
sumax+=pq.top(),pq.pop();
out<<sumax;
return 0;
}