Cod sursa(job #163681)

Utilizator bazubBazu Bogdan bazub Data 22 martie 2008 14:54:58
Problema Peste Scor 20
Compilator cpp Status done
Runda preONI 2008, Runda Finala, Clasa a 10-a Marime 1.38 kb
#include<fstream.h>
long long cati,max;
long i,j,n,k,tt,fr[50005];
struct{
	 int p;
	 int t;
}pls[50005],pla[50005];
void ms(long st, long dr){
	 int i,m,k;
	 if(st<dr){
		  m=(st+dr)/2;
		  ms(st,m);
		  ms(m+1,dr);
		  j=m+1;
		  k=st-1;
        for(i=st;i<=m;i++){
            while(pls[i].t>pls[j].t && j<=dr){
                k++;
                pla[k]=pls[j];
                j++;
            }
            
            k++;
            pla[k]=pls[i];
        }
        for(i=j;i<=dr;i++){
            k++;
            pla[k]=pls[i];
        }
        for(i=st;i<=dr;i++)
            pls[i]=pla[i]; 
    }  
}
long long cmax(long i){
    long j=1,l;
    long long c=0;
    for(j=1;j<=1000;j++)
		  fr[j]=0;
	j=1;
	 while(pls[j].t<=i && j<=n){
        fr[pls[j].p]++;
        j++;
    }    
    j=0;
    l=1000;
	 while(j<k && l>0){
        while(fr[l]>0 && j<=k){
            fr[l]--;
            j++;
            c+=l;
        }
        l--;
    }
    return c;   
}
int main(){
    ifstream fin("peste.in");
    ofstream fout("peste.out");
    fin>>n>>k>>tt;
    for(i=1;i<=n;i++){
        fin>>pls[i].p;
        fin>>pls[i].t;
    }
    ms(1,n);
    for(i=1;i<=tt;i++){
        cati=cmax(i);
        cati*=tt/i;
        if(cati>max)
            max=cati;
    }
    fout<<max;    
    fin.close();
    fout.close();
    return 0;
}