Pagini recente » Cod sursa (job #1299291) | Cod sursa (job #318031) | Cod sursa (job #639395) | Cod sursa (job #25007) | Cod sursa (job #166335)
Cod sursa(job #166335)
#include <stdio.h>
#include <algorithm>
const int nm = 50010;
#define p first
#define t second
using namespace std;
pair<int, int> plasa[nm];
int v[nm], c[nm], h[nm], N, K, T, sum;
void up(int);
void down(int);
int main()
{
freopen("peste.in", "r", stdin);
freopen("peste.out", "w", stdout);
int i, j;
scanf("%d %d %d", &N, &K, &T);
for(i = 1; i <= N; ++i)
{
scanf("%d %d", &plasa[i].p, &plasa[i].t);
}
sort(plasa + 1, plasa + N + 1);
for(i = 1; i <= N; ++i)
{
if(i <= K)
{
h[++h[0]] = plasa[i].p;
up(h[0]);
sum += plasa[i].p;
}
else
{
if(plasa[i].p > h[1])
{
sum -= h[1];
sum += plasa[i].p;
h[1] = plasa[i].p;
down(1);
}
}
if(v[plasa[i].t] < sum)
{
v[plasa[i].t] = sum;
}
}
/*
for(i = 1; i <= T; ++i)
{
printf("%d\n", v[i]);
}
*/
for(i = 1; i <= T; ++i)
{
for(j = 1; j <= 1000 && j <= i; ++j)
{
if(c[i] < c[i - j] + v[j])
{
c[i] = c[i - j] + v[j];
}
}
}
printf("%d\n", c[T]);
return 0;
}
void up(int nod)
{
if(nod != 1)
{
int dad = nod / 2, temp;
if(h[nod] < h[dad])
{
temp = h[nod];
h[nod] = h[dad];
h[dad] = temp;
up(dad);
}
}
}
void down(int nod)
{
int l = 2 * nod, r = 2 * nod + 1, temp, best = nod;
if(l <= h[0] && h[l] < h[best])
{
best = l;
}
if(r <= h[0] && h[r] < h[best])
{
best = r;
}
if(best != nod)
{
temp = h[best];
h[best] = h[nod];
h[nod] = temp;
down(best);
}
}