Cod sursa(job #1051555)

Utilizator adalLica Adela adal Data 10 decembrie 2013 11:42:50
Problema Lupul Urias si Rau Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.03 kb
#include <cstdio>
#include <vector>
#include <algorithm>
#include <set>
#define mp make_pair
#define pb push_back
#define s second
#define f first

using namespace std;

vector<pair<int,int> > V;
vector<pair<int,int> >::iterator it;

multiset<int> H;
multiset<int>::iterator ultim;

int N, L, K, c, i, x;
long long Cost;

bool cmp(pair<int,int> X, pair<int,int> Y)
{
    if (X.s >Y.s) return true;
    return false;
}

int main()
{
    freopen("lupu.in", "r", stdin);
    freopen("lupu.out", "w", stdout);
    scanf("%d %d %d\n", &N, &L, &K);
    for (i=1; i<=N; i++)
    {
        scanf("%d %d\n", &x, &c);
        V.pb( mp( c, (L-x)/K + 1 ) );
    }

    sort(V.begin(), V.end(), cmp);

    it=V.begin();

    for( x=V.begin()->s; x>0; x--)
    {
        for( ; it->s==x && it!=V.end(); it++)
            H.insert( it->f );
        if (!H.empty()) {
            ultim=H.end(); ultim--;
            Cost+=*ultim;
            H.erase(ultim);
        }
    }
    printf("%lld\n", Cost);
    return 0;
}