Cod sursa(job #163604)

Utilizator za_wolfpalianos cristian za_wolf Data 22 martie 2008 14:48:37
Problema Peste Scor 0
Compilator cpp Status done
Runda preONI 2008, Runda Finala, Clasa a 10-a Marime 1.53 kb
#include<stdio.h>
#include<algorithm>
#define NMAX 50011
using namespace std;
long poz,ww,tc,j,in,mmax,sf,n,i,a,k,T,ii,rez,w,z[NMAX];
struct kkt
{
    long P,T;
};
kkt xx[NMAX],x[NMAX],y[NMAX];
int cmpf1(const kkt a, const kkt b)
{
    double A,B;
    A=(double)a.P/a.T;
    B=(double)b.P/b.T;

    return ((A-B>0));
}

int cmpf2(const kkt a, const kkt b)
{
    double A,B;
    A=(double)a.P/a.T;
    B=(double)b.P/b.T;
    if (A-B>=0&&a.T>b.T)
        return 1;
        return 0;
}
int main()
{
    freopen("peste.in","r",stdin);
    freopen("peste.out","w",stdout);
    scanf("%ld%ld%ld",&n,&k,&T);
    for (i=1;i<=n;i++)
    {
        scanf("%ld%ld",&x[i].P,&x[i].T);
        xx[i]=x[i];
    }

    sort(x+1,x+n+1,cmpf1);

    sort(x+1,x+n+1,cmpf2);


    in=1;
    sf=0;
    tc=0;
    while (tc<T)
    {
        y[++sf]=x[1];
        z[1]=1;
        for (j=2;j<=n&&sf-in+1<k;j++)
            if (z[j]==0&&x[j].T+tc<=T&&x[j].T<=y[in].T)
            {
                z[j]=1;
                y[++sf]=x[j];
                y[sf].T+=tc;
                
            }

        mmax=-1;
        rez+=y[in].P;
        for (i=in;i<=sf;i++)
            if (y[i].T>mmax)
                mmax=y[i].T;

        tc+=mmax;
        mmax=10001;
        for (i=in;i<=sf;i++)
            if (mmax>y[i].T)
            {
                mmax=y[i].T;
                poz=i;
            }

        in++;

    }
    for (i=in;i<=sf;i++)
        rez+=y[i].P;
    printf("%ld\n",rez);

    return 0;
}