Cod sursa(job #1258019)

Utilizator the@EyE@Postavaru Stefan the@EyE@ Data 8 noiembrie 2014 13:17:14
Problema Lupul Urias si Rau Scor 16
Compilator cpp Status done
Runda Teme Pregatire ACM Unibuc 2014, Anul II Marime 1.06 kb
#include<stdio.h>
#include<algorithm>
#include<vector>
#include<queue>

using namespace std;

int n,l,x,maxT=-1,ras=0;

struct sheep{
  int d,v,t;

  sheep(int d,int v)
  {
      this->d = d;
      this->v = v;
      t = (x-d)/l;
      if(t>maxT)maxT=t;
  }

  sheep(){}
};

bool cmp(const sheep &a,const sheep &b)
{
    return a.t>b.t;
}

class heap_cmp
{
    public: bool operator()(const sheep &a,const sheep &b)
    {
        return a.v<b.v;
    }
};

priority_queue<sheep,vector<sheep>,heap_cmp> heap;
deque<sheep> sheeps;

int main()
{
    freopen("lupu.in","r",stdin);
    freopen("lupu.out","w",stdout);
    scanf("%d%d%d",&n,&x,&l);
    for(int i=0;i<n;++i)
    {
        int d,v;
        scanf("%d%d",&d,&v);
        sheep s(d,v);
        sheeps.push_back(s);
    }
    sort(sheeps.begin(),sheeps.end(),cmp);
    for(int i=maxT;i>=0;i--)
    {
        while(sheeps[0].t==i){heap.push(sheeps[0]);sheeps.pop_front();}
        if(heap.size()>0){ras+=heap.top().v;heap.pop();}
    }
    printf("%d\n",ras);
    return 0;
}