Cod sursa(job #205151)

Utilizator toni2007Pripoae Teodor Anton toni2007 Data 29 august 2008 15:33:44
Problema Peste Scor 90
Compilator c Status done
Runda Arhiva de probleme Marime 1.93 kb
#include <stdio.h>
#include <stdlib.h>
#define N 50010
int p[N],t[N];
int n,k,T;
void scan(void){
	int i;
	freopen("peste.in","r",stdin);
	freopen("peste.out","w",stdout);
	scanf("%d%d%d",&n,&k,&T);
	for (i=1;i<=n;++i)
		scanf("%d%d",&p[i],&t[i]);
}
int cmp(int a,int b){
	if (t[a]!=t[b])
		return t[a]-t[b];
	return p[a]-p[b];
}
void swap_2(int i,int j){
	int aux;
	aux=p[i];
	p[i]=p[j];
	p[j]=aux;
	aux=t[i];
	t[i]=t[j];
	t[j]=aux;
}
void down_heap_2(int i,int n){
	int max=i;
	if (2*i<=n && cmp(max,2*i)<0)
		max=2*i;
	if (2*i+1<=n && cmp(max,2*i+1)<0)
		max=2*i+1;
	if (i!=max){
		swap_2(i,max);
		down_heap_2(max,n);
	}
}
void sort_t(void){
	int i;
	for (i=n/2;i>=1;--i)
		down_heap_2(i,n);
	for (i=n;i>1;--i){
		swap_2(1,i);
		down_heap_2(1,i-1);
	}
}
long long suma;
int h[N],nn;
long long aux[N],best[N];
int TMAX;
void swap(int i,int j){
	int auxa;
	auxa=h[i];
	h[i]=h[j];
	h[j]=auxa;
}
void down_heap(int i,int n){
	int max=i;
	if (2*i<=n && h[max]>h[2*i])
		max=2*i;
	if (2*i+1<=n && h[max]>h[2*i+1])
		max=2*i+1;
	if (i!=max){
		swap(i,max);
		down_heap(max,n);
	}
}
void update(int x){
	if (nn<k){
		h[++nn]=x;
		suma+=(long long)x;
		down_heap(1,nn);
		return ;
	}
	if (x<h[1])
		return ;
	suma+=(long long)(x-h[1]);h[1]=x;
	down_heap(1,nn);
}
void make_aux(){
	int st=0,i;
	for (i=1;i<=T;++i){
		while (t[st+1]<=i && st<n){
			update(p[++st]);
			aux[i]=suma;
		}
	}
    TMAX=t[n];
}
long long max(long long a,long long b){
	if (a>b)
		return a;
	return b;
}
int min(int a,int b){
     if (a>b)
        return b;
     return a;
}
void solve_it(){
	int i,j;
	for (i=1;i<=T;++i){
		for (j=1;j<=min(i,TMAX);++j)
			best[i]=max(best[i],(long long)best[i-j]+(long long)aux[j]);
	}
}
void print_sol(){
	printf("%lld\n",best[T]);
	fclose(stdin);
	fclose(stdout);
	exit(0);
}
int main(void){
	scan();
	sort_t();
	make_aux();
	solve_it();
	print_sol();
}