Cod sursa(job #1413018)

Utilizator delia_99Delia Draghici delia_99 Data 1 aprilie 2015 18:06:54
Problema Peste Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.26 kb
#include <cstdio>
#include <algorithm>
using namespace std;
int n,k,t,i,x,y,nr,sum=0,Max,start,stop;
bool ok;
struct gigel
{
    int pesti,timp;
};
gigel v[50010];

inline int maxim(int a,int b)
{
    if(a<b)
        return b;
    return a;
}

inline int minim(int a,int b)
{
    if(a<b)
        return a;
    return b;
}

inline bool cmp(gigel a,gigel b)
{
    if(a.pesti>b.pesti)
        return true;
    if(a.pesti==b.pesti && a.timp<=b.timp)
        return true;
    return false;
}

int main()
{
    freopen("peste.in","r",stdin);
    freopen("peste.out","w",stdout);
    scanf("%d %d %d\n",&n,&k,&t);
    nr=0;
    for(i=1; i<=n; ++i)
    {
        scanf("%d %d\n",&x,&y);
        if(y<=t)
            v[++nr].pesti=x,v[nr].timp=y;
    }
    if(nr!=0)
        sort(v+1,v+nr+1,cmp);
    else
    {
        printf("0\n");
        return 0;
    }
    start=1;
    while(t>0 && start<=nr)
    {
        i=1;
        Max=0;
        while(i<=k && start<=nr)
        {
            if(v[i].timp<=t)
            {
                sum+=v[i].pesti;
                Max=maxim(Max,v[i].timp);
                ++i;
            }
            ++start;
        }
        t-=Max;
    }
    printf("%d\n",sum);
    return 0;
}