Cod sursa(job #778298)

Utilizator ionut_blesneagIonut Blesneag ionut_blesneag Data 14 august 2012 14:16:06
Problema Lupul Urias si Rau Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.77 kb
#include<fstream>
#include<algorithm>
#include<vector>
using namespace std;
int n,x,l,d,a,i,j,tmax,sum;

ifstream f("lupu.in");
ofstream g("lupu.out");

struct sheep {int dist; int wool;};
sheep v[100001];
vector<int> h;

struct comp
{bool operator()(const sheep &a, const sheep &b) const
       {
       return (a.dist>b.dist);
       }
};

int main()
{f>>n>>x>>l;
for(i=1; i<=n; i++)
  {f>>d>>a;
   v[i].dist=(x-d)/l;
   v[i].wool=a;
   }
sort(v+1,v+n+1,comp()); 
tmax=v[1].dist;
i=1;
make_heap(h.begin(), h.end());
for(j=tmax; j>=0; j--)
{
while(v[i].dist==j) {h.push_back(v[i].wool); push_heap (h.begin(),h.end()); i++;}
if(!h.empty())
{sum+=h.front();
 pop_heap (h.begin(),h.end()); h.pop_back();}
}
g<<sum;   
f.close();
g.close();
return 0;}