Cod sursa(job #1244932)

Utilizator vasica38Vasile Catana vasica38 Data 18 octombrie 2014 13:56:50
Problema Gutui Scor 100
Compilator cpp Status done
Runda teme_upb Marime 1.29 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;
};


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

int x,y;
struct gutui1
{
    int r;
    int l;
};
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<int> q;

    sort(a+1,a+n+1,cmp);
    //for (i=1; i<=n; ++i) printf("%d %d\n",a[i].r,a[i].l);
    int u1=height;
    while (u1-u>=a[1].r) u1-=u;
    int poz=1;
    bool ok=true;
    while(ok)
    {
    if (a[poz].r>u1 || poz>n)
    {
        if (!q.empty())
        {
            sol+=q.top();
            q.pop();
        }
        u1+=u;
        if (u1>height ) ok = false;
    }
    else
        if(a[poz].r<=u1 && poz<=n)
        {
        q.push(a[poz].l);
        ++poz;
        }
    }
    printf("%lld",sol);
    return 0;

}