Cod sursa(job #163601)

Utilizator Adriana_SAdriana Sperlea Adriana_S Data 22 martie 2008 14:48:33
Problema Peste Scor 0
Compilator cpp Status done
Runda preONI 2008, Runda Finala, Clasa a 10-a Marime 1.16 kb
#include <stdio.h>
#include <algorithm>
#include <vector>

using namespace std;

const int N_MAX = 50010;

struct und {
	int P, T;
} v[N_MAX];

int tp[N_MAX];
char used[N_MAX];

pair <int, int> pot[N_MAX];

int cmp(pair <int, int> a, pair <int, int> b)
{
	return (a.first > b.first);
}

int main()
{
	freopen("peste.in", "r", stdin);
#ifndef _SCREEN_
	freopen("peste.out", "w", stdout);
#endif

	int K, N, TT;
	scanf("%d %d %d\n", &N, &K, &TT);
	for (int i = 1; i <= N; i ++) {
		scanf("%d %d\n", &v[i].P, &v[i].T);
		pot[i] = make_pair((TT / v[i].T) * v[i].P, i);
	}

	sort(pot + 1, pot + N + 1, cmp);

	int rez = 0;
	for (int i = 1; i <= K; i ++) {
		used[pot[i].second] = 1;
		rez += pot[i].first;

		tp[i] = (TT % v[pot[i].second].T);
	}

	int g = 1, MAX, poz;
	while (g) {

		g = 0;
		for (int i = 1; i <= K; i ++) {
			
			MAX = 0, poz = 0;
			for (int j = 1; j <= N; j ++) {
				if (!used[j] && ((tp[i] / v[j].T) * v[j].P > MAX)) {
					MAX = (tp[i] / v[j].T) * v[j].P;
					poz = j;
				}
			}

			if (!poz) tp[i] = 0;
			else {
				used[poz] = 1;
				g = 1;
				rez += (tp[i] / v[poz].T) * v[poz].P;
				tp[i] = (tp[i] % v[poz].T);
			}
		}
	}

	printf("%d\n", rez);

	return 0;
}