Cod sursa(job #2032240)

Utilizator Ruxandra985Nanu Ruxandra Laura Ruxandra985 Data 4 octombrie 2017 18:57:44
Problema Peste Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.66 kb
#include <cstdio>
#include <algorithm>

using namespace std;
pair <int,int> v[50001],h[50001],h2[50001];
int elem,elem2;
int cmp (pair <int,int> a, pair <int,int> b){
    if (a.first==b.first)
        return a.second>b.second;
    else return a.first<b.first;
}
int compar (int a,int b){
    int x,y,z,t;
    x=h[a].first;
    y=h[a].second;
    z=h[b].first;
    t=h[b].second;
    return (x*t>z*y);
}
void adauga (int a,int b){
    int p,c;
    elem++;
    h[elem].first=a;
    h[elem].second=b;
    c=elem;
    p=elem/2;
    while (p>0){
        if (compar (c,p))
            swap (h[c],h[p]);
        else break;
        c=p;
        p/=2;
    }
}
void sterge (int poz){
    int p,c;
    h[poz].first=h[elem].first;
    h[poz].second=h[elem].second;
    elem--;
    p=poz;
    c=2*poz;
    while (c<=elem){
        if (c+1<=elem && h[c+1]>h[c])
            c++;
        if (compar (c,p))
            swap (h[c],h[p]);
        else break;
        p=c;
        c*=2;
    }
}
void adg (int a,int b){
    int p,c;
    elem2++;
    h2[elem2].first=a;
    h2[elem2].second=b;
    c=elem2;
    p=elem2/2;
    while (p>0){
        if ((h2[c].first<h2[p].first) || (h2[c].first == h2[p].first && h2[c].second<h2[p].second))
            swap (h2[c],h2[p]);
        else break;
        c=p;
        p/=2;
    }
}
void stg (int poz){
    int p,c;
    h2[poz].first=h2[elem2].first;
    h2[poz].second=h2[elem2].second;
    elem2--;
    p=poz;
    c=2*poz;
    while (c<=elem2){
        if (c+1<=elem2 && h2[c+1]<h2[c])
            c++;
        if ((h2[c].first<h2[p].first) || (h2[c].first == h2[p].first && h2[c].second<h2[p].second))
            swap (h2[c],h2[p]);
        else break;
        p=c;
        c*=2;
    }
}
int main()
{
    FILE *fin=fopen ("peste.in","r");
    FILE *fout=fopen ("peste.out","w");
    int n,k,t,s,sol,i;
    fscanf (fin,"%d%d%d",&n,&k,&t);
    for (i=1;i<=n;i++)
        fscanf (fin,"%d%d",&v[i].second,&v[i].first);
    sort (v+1,v+n+1,cmp);
    s=0;
    // h2.first = nr pesti
    // h2. second = minute
    for (i=1;i<=k;i++){
        s=s+v[i].second;
        adg (v[i].second,v[i].first);
        adauga (s,v[i].first);
        //printf ("%d %d\n",s,v[i].first);
    }
    for (;i<=n;i++){
        s-=h2[1].first;
        stg (1);
        s+=v[i].second;
        adg (v[i].second,v[i].first);
        adauga (s,v[i].first);
        //printf ("%d %d\n",s,v[i].first);
    }
    sol=0;
    while (elem){
        if (t-h[1].second>=0){
            t-=h[1].second;
            sol+=h[1].first;
        }
        else sterge (1);
    }
    fprintf (fout,"%d",sol);
    return 0;
}