Cod sursa(job #1862015)

Utilizator ionanghelinaIonut Anghelina ionanghelina Data 29 ianuarie 2017 14:35:52
Problema Gutui Scor 100
Compilator cpp Status done
Runda teme_upb Marime 0.83 kb
#include<bits/stdc++.h>
using namespace std;
priority_queue<int,vector<int>,less<int> > q;
pair<int,int> v[100005];
bool cmp(pair<int,int> a,pair<int,int> b)
{
    return a.first>b.first;
}
int n,height,maxt,u,x,y,t;
long long sol;
int main()
{
    freopen("gutui.in","r",stdin);
    freopen("gutui.out","w",stdout);
    scanf("%d%d%d",&n,&height,&u);
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d",&x,&y);
        t=(height-x)/u;
        v[i]=make_pair(t,y);
    }
    sort(v+1,v+n+1,cmp);
        maxt=v[1].first;
    int i=1;
    for(int t=maxt;t>=0;t--)
    {
        while(i<=n && v[i].first>=t)
        {
            q.push(v[i].second);
            i++;
        }
       if(!q.empty())
       {
        sol=sol+1LL*q.top();
        q.pop();
       }
    }
    printf("%lld\n",sol);
    return 0;
}