Cod sursa(job #2032520)

Utilizator Ruxandra985Nanu Ruxandra Laura Ruxandra985 Data 5 octombrie 2017 10:10:14
Problema Peste Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.74 kb
#include <cstdio>
#include <algorithm>

using namespace std;
pair <int,int> v[50001],h[50001],h2[50001];
long long d[50001];
int w[1001];
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 && compar (c+1,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)
            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].first<h2[c].first)
            c++;
        if (h2[c].first<h2[p].first)
            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,i;
    long long sol;
    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);
        w[v[i].first]=max(w[v[i].first],s);
        //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);
        w[v[i].first]=max(w[v[i].first],s);
        //adauga (s,v[i].first);
        //printf ("%d %d\n",s,v[i].first);
    }
    for (i=1;i<=1000;i++)
        w[i]=max(w[i],w[i-1]);
    for (i=1;i<=t;i++){
        for (int j=1;j<=1000 && i>=j;j++)
            d[i]=max(d[i],w[j]+d[i-j]);
        //printf ("%d\n",d[i]);
    }
    fprintf (fout,"%lld",d[t]);
    return 0;
}