Cod sursa(job #992131)

Utilizator Impaler_009Mihai Nitu Impaler_009 Data 1 septembrie 2013 09:42:43
Problema Lupul Urias si Rau Scor 68
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.24 kb
#include <fstream>
#include <vector>
#include <algorithm>

#define maxn 100005

using namespace std;

ifstream fin("lupu.in");
ofstream fout("lupu.out");

vector <int> V[maxn];
int moments[maxn];
bool picked[maxn];

struct sheep
{
    int x,d;
}v[maxn];

int n,s,x,l,m,t,maxv,cnt,maxi;

int main()
{
    fin>>n>>x>>l;
    for (int i=1; i<=n; ++i)
        fin>>v[i].d>>v[i].x;

    for (int i=1; i<=n; ++i)
    {
        m = (x-v[i].d)/l;

        //if (x-v[i].d<0) continue;
        //if (m>100000) m=100001;

        if (!picked[m])
        {
            moments[++t] = m;
            picked[m] = 1;
        }
        V[m].push_back(v[i].x);
    }

    sort (moments+1, moments+t+1);

    for (int i=1; i<=t; ++i)
    {
        sort (V[moments[i]].begin(),V[moments[i]].end());
    }

    cnt = moments[t];

    for (cnt = moments[t]; cnt>=0; --cnt)
    {
        maxv=0;
        for (int i=t; moments[i]>=cnt && i>=0; --i)
        {
            if (!V[moments[i]].empty() && V[moments[i]].back()>maxv)
            {
                maxv=V[moments[i]].back();
                maxi=moments[i];
            }
        }

        s+=maxv;
        if (maxv!=0) V[maxi].pop_back();
    }

    fout<<s;
}