Cod sursa(job #204687)

Utilizator gabitzish1Gabriel Bitis gabitzish1 Data 26 august 2008 14:15:12
Problema Peste Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.68 kb
#include <stdio.h>

int N, K, TTotal, v[50005], aux[1005];

typedef struct
{
	int x, t;
} Peste;
Peste a[50005];

int main()
{
	freopen("peste.in","r",stdin);
	freopen("peste.out","w",stdout);
	
	int i, j, tmax = 0, max;
	scanf("%d %d %d", &N, &K, &TTotal);
	for (i = 1; i <= N; i++) 
	{
		scanf("%d %d", &a[i].x, &a[i].t);
		if (a[i].t > tmax) tmax = a[i].t;
	}

	for (i = 1; i <= N; i++)
		for (j = a[i].t; j <= tmax; j++) aux[j] += a[i].x;

	for (i = 1; i <= TTotal; i++)
	{
		max = 0;
		for (j = i - 1; j >= 0 && j >= i - tmax; j--) 
			if (v[j] + aux[i - j] > max) max = v[j] + aux[i - j];
		v[i] = max;
	}

	printf("%d\n",v[TTotal]);
	return 0;
}