Cod sursa(job #205145)

Utilizator toni2007Pripoae Teodor Anton toni2007 Data 29 august 2008 15:17:45
Problema Peste Scor 0
Compilator c Status done
Runda Arhiva de probleme Marime 1.95 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);
	}
}
int suma;
int h[N],nn,aux[N];
int TMAX;
int best[N];
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+=x;
		down_heap(1,nn);
		return ;
	}
	if (x<h[1])
		return ;
	suma+=(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]);
		}
		if (nn==k)
				aux[i]=suma;
		//printf("%d %d\n",i,st);
	}
	//for (i=1;i<=T;++i)
		//printf("%d ",aux[i]);
	TMAX=t[n];
}
int max(int a,int b){
	if (a>b)
		return a;
	return b;
}
void solve_it(){
	int i,j;
	for (i=1;i<=TMAX;++i)
		best[i]=aux[i];
	for (i=TMAX+1;i<=T;++i){
		for (j=1;j<=TMAX;++j)
			best[i]=max(best[i],best[i-j]+aux[j]);
	}
}
void print_sol(){
	//if (T<=TMAX)
		//best[T]=aux[T];
	printf("%d\n",best[T]);
	fclose(stdin);
	fclose(stdout);
	exit(0);
}
int main(void){
	scan();
	sort_t();
	make_aux();
	solve_it();
	print_sol();
}