Pagini recente » Istoria paginii runda/concurs_informatica/clasament | Rezultatele filtrării | Cod sursa (job #2885516) | Istoria paginii utilizator/jmeky | Cod sursa (job #204704)
Cod sursa(job #204704)
#include <stdio.h>
int N, K, TTotal, v[50005], aux[1005], h1[50005], h2[50005], k1, k2, nr;
typedef struct
{
int x, t;
} Peste;
Peste a[50005];
void swap(int &x, int &y)
{
int t = x; x = y; y = t;
}
void urc1(int poz)
{
if (poz / 2 >= 1)
if (a[ h1[poz] ].t < a[ h1[poz / 2] ].t)
{
swap(h1[poz], h1[poz / 2]);
urc1(poz / 2);
}
}
void urc2(int poz)
{
if (poz / 2 >= 1)
if (a[ h2[poz] ].x > a[ h2[poz / 2] ].x)
{
swap(h2[poz], h2[poz / 2]);
urc2(poz / 2);
}
}
void cobor(int poz)
{
int st, dr, m;
st = poz * 2;
dr = st + 1;
m = poz;
if (st <= k1) if (a[ h1[poz] ].t > a[ h1[st] ].t) m = st;
if (dr <= k1) if (a[ h1[m] ].t > a[ h1[dr] ].t) m = dr;
if (m != poz)
{
swap(h1[m], h1[poz]);
cobor(m);
}
}
void cobor2(int poz)
{
int st, dr, m;
st = poz * 2;
dr = st + 1;
m = poz;
if (st <= k2) if (a[ h2[poz] ].x < a[ h2[st] ].x) m = st;
if (dr <= k2) if (a[ h2[m] ].x < a[ h2[dr] ].x) m = dr;
if (m != poz)
{
swap(h2[m], h2[poz]);
cobor2(m);
}
}
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;
h1[++k1] = i;
urc1(k1);
}
for (i = 1; i <= tmax; i++)
{
while (a[ h1[1] ].t == i && k1)
{
h2[++k2] = h1[1];
urc2(k2);
swap(h1[1],h1[k1]); k1--;
cobor(1);
nr++;
}
for (j = 1; j <= K && k2 >= 1; j++)
{
aux[i] += a[ h2[1] ].x;
swap(h2[1],h2[k2]); k2--;
cobor2(1);
}
for (j = k2 + 1; j <= nr; j++) { k2++; urc2(j); }
}
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;
}