Cod sursa(job #87077)

Utilizator DastasIonescu Vlad Dastas Data 26 septembrie 2007 15:40:01
Problema Lupul Urias si Rau Scor 16
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.44 kb
#include <cstdio>
#include <algorithm>

const int maxn = 100001;

FILE *in = fopen("lupu.in","r"), *out = fopen("lupu.out","w");

struct oaie
{
    int D, A;
};

int n, x, l;
oaie a[maxn];
int T[maxn]; // timpul maxim la care oaia i poate fi aleasa
int tkn[maxn]; // 1 daca am ales o oaie la momentul i

bool operator<(const oaie &x, const oaie &y)
{
    return x.A > y.A;
}

void read()
{
    fscanf(in, "%d %d %d", &n, &x, &l);

    for ( int i = 1; i <= n; ++i )
        fscanf(in, "%d %d", &a[i].D, &a[i].A);
}

int search(int tmax)
{
    int st = 1, dr = n;

    int r = 0;
    while ( st <= dr )
    {
        int m = ( st + dr ) >> 1;
        if ( m > tmax )
            dr = m - 1;
        else if ( m <= tmax )
        {
            st = m + 1;
            if ( !tkn[m] )
                r = m;
        }
       // else if ( !tkn[m] )
         //   return m;
    }

    return r;
}

int main()
{
    read();
    std::sort(a+1, a+1+n);

    for ( int i = 1; i <= n; ++i )
    {
        int p = 0;
        while ( p + a[i].D <= x )
            ++T[i], p += l;
    }

    int answ = 0;
//    for ( int i = 1; i <= n; ++i )
//        printf("%d %d %d\n", a[i].D, a[i].A, T[i]);

    for ( int i = 1; i <= n; ++i )
    {
        int t = search( T[i] );
        //printf("%d\n", t);
        if ( t )
            answ += a[i].A, tkn[t] = 1;
    }

    fprintf(out, "%d\n", answ);

	return 0;
}