Cod sursa(job #2428755)

Utilizator mihai2003LLL LLL mihai2003 Data 6 iunie 2019 11:44:58
Problema Lupul Urias si Rau Scor 92
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.93 kb
#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;
}