Pagini recente » Cod sursa (job #551283) | Cod sursa (job #1188953) | Cod sursa (job #2880646) | Cod sursa (job #835775) | Cod sursa (job #163601)
Cod sursa(job #163601)
#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;
}