Cod sursa(job #1318565)

Utilizator ThomasFMI Suditu Thomas Thomas Data 16 ianuarie 2015 09:29:52
Problema Lupul Urias si Rau Scor 100
Compilator cpp Status done
Runda Teme Pregatire ACM Unibuc 2014, Anul I Marime 1.92 kb
#include <fstream>
#include <algorithm>
#include <set>
using namespace std;
  
#define NMax 100005
#define inf 2147483647
  
ifstream f("lupu.in");
ofstream g("lupu.out");
  
int n,x,l;
long long sol;
  
struct oaie{int d,c;};
oaie v[NMax];
  
bool Compare(oaie i,oaie j)
{
    if(i.c!=j.c) return i.c>j.c;
    else return i.d<j.d;
}
  
struct mult{
    int l1,l2;
  
    bool operator< (const mult &t) const
    {
        return t.l2<l1;
    }
  
    bool operator> (const mult &t) const
    {
        return t.l1>l2;
    }
  
    bool operator== (const mult &t) const
    {
        return t.l1>=l1 && t.l2<=l2;
    }
}u;
  
set<mult> A;
set<mult>::iterator it,it2;
  
int main()
{
    int i,a,b;
  
    f>>n>>x>>l;
    for(i=1;i<=n;++i)
    {
        f>>b>>a;
        if(b>x) continue;
        v[i].c=a;
        v[i].d=(x-b)/l+1;
    }
  
    sort(v+1,v+n+1,Compare);
  
    int add;
    for(i=1;i<=n;++i)
    {
        add=0;
        u.l1=u.l2=v[i].d;
  
        it=A.find(u);
        if(it==A.end()) {A.insert(u);add=1;}
        else
        {
            do
            {
                u.l1=u.l2=(*it).l1-1;
                if((*it).l1-1==0) break;
                it2=A.find(u);
                if(it2==A.end())
                {
                    u.l1=(*it).l1-1;
                    u.l2=(*it).l2;
                    A.erase(it);
                    A.insert(u);
                    add=1;
                    break;
                }
                else
                {
                    u.l1=(*it2).l1;
                    u.l2=(*it).l2;
                    A.erase(it);
                    A.erase(it2);
                    A.insert(u);
                    it=A.find(u);
                }
            } while(1);
        }
  
        if(add==1) sol+=(long long)v[i].c;
    }
  
    g<<sol<<"\n";
  
    f.close();
    g.close();
    return 0;
}