Pagini recente » Cod sursa (job #1405741) | Cod sursa (job #2929636) | Cod sursa (job #2841771) | Cod sursa (job #2261629) | Cod sursa (job #163681)
Cod sursa(job #163681)
#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;
}