Cod sursa(job #1173549)

Utilizator andreiagAndrei Galusca andreiag Data 20 aprilie 2014 00:07:53
Problema Lupul Urias si Rau Scor 28
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.86 kb
#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;
typedef long long ll;
typedef pair<int, int> oaie;    // oaie = pair<distanta, lana>
const int Nmax = 100111;

class pufos_functor{
public:
    pufos_functor(int X, int L): distmax(X), increment(L) { }
    bool operator() (const oaie &A, const oaie &B) const
    {
        //if (A.first > distmax) return 1;
        //if (B.first > distmax) return 0;
        return ((distmax - A.first) / increment < (distmax - B.first) / increment) ||
                (((distmax - A.first) / increment == (distmax - B.first) / increment)
                    && (A.second >= B.second));
    }
private:
    int distmax, increment;
};

oaie ferma[Nmax];

inline int max(int x, int y) { return x > y ? x : y; }

int main()
{
    ifstream f ("lupu.in");
    ofstream g ("lupu.out");

    int N, X, L, D, A;
    f >> N >> X >> L;
    for (int i = 0; i < N; i++)
    {
        f >> D >> A;
        if (D > X) { --i; --N; }
        else { ferma[i].first = D; ferma[i].second = A; }
    }

    sort(ferma, ferma + N, pufos_functor(X, L));
    
    ll lana = 0;
    int pas = 0;
    //int best = 0;
    for (int i = 0; i < N; i++)
    {
        if (1ll*pas*L + ferma[i].first > X) continue;
        /*
        if (ferma[i].first + 1ll*(pas+1)*L > X)
        {
            best = max(best, ferma[i].second);
        }
        if (ferma[i].first + 1ll*(pas+1)*L <= X)
        {
            if (best)
            {
                i--;
                lana += best;
                best = 0;
                pas++;
            }
            else
            {
                // ???
            }
        }
        */
        lana += ferma[i].second;
        pas++;
    }
    g << lana << '\n';
    /*
    g << "distanta: lana\n";
    for (int i = 0; i < N; i++)
        g << ferma[i].first << ":\t" << ferma[i].second << '\n';
    */
    return 0;
}