Cod sursa(job #1244847)

Utilizator vasica38Vasile Catana vasica38 Data 18 octombrie 2014 12:11:27
Problema Gutui Scor 10
Compilator cpp Status done
Runda teme_upb Marime 1.3 kb
#include<queue>
#include<vector>
#include<stdio.h>
#include<math.h>
#include<algorithm>

using namespace std;

struct gutui
{
    gutui(int x, int y): x1(x), y1(y){}
    int x1;
    int y1;
};

int x,y;
struct gutui1
{
    int r;
    int l;
};

bool operator>(const  gutui &o1, const gutui &o2)
{
    return o1.x1<o2.x1;
}


bool cmp(gutui1 o1, gutui1 o2)
{
    if (o1.r==o2.r) return o1.l>o2.l;
        else return o1.r>o2.r;
}


gutui1 a[100005];
int i,j,k,m,n,u,weight;
long long sol;


int height;
int main()
{
    freopen("gutui.in","r",stdin);
    freopen("gutui.out","w",stdout);
    scanf("%d%d%d",&n,&height,&u);
    for (i=1; i<=n; ++i) scanf("%d%d",&a[i].r,&a[i].l);

    priority_queue<gutui, vector<gutui> , greater<gutui> >q;

    sort(a+1,a+n+1,cmp);
    //for (i=1; i<=n; ++i) printf("%d %d\n",a[i].r,a[i].l);
    for (i=1; i<=n; ++i)
    {
        if (a[i].r<=height)  q.push(gutui(a[i].r,a[i].l));

    }
    bool ok=true;
    int nivel=0;
    i=0;
    while (ok)
    {
    ++i;
    gutui r=q.top();
    //printf("%d %d\n",r.x1,r.y1);
    if (r.x1+nivel<=height)
    {
        sol+=r.y1;
        q.pop();
        nivel+=u;
    }
    else
    {
        q.pop();
    }
    if (i>n) ok=false;
    }
    printf("%d\n",sol);
    return 0;

}