Mai intai trebuie sa te autentifici.
Cod sursa(job #163668)
Utilizator | Data | 22 martie 2008 14:52:58 | |
---|---|---|---|
Problema | Peste | Scor | 0 |
Compilator | cpp | Status | done |
Runda | preONI 2008, Runda Finala, Clasa a 9-a | Marime | 1.49 kb |
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
#define t first
#define p second
#define NMAX 50005
vector<pair<int,int> > V;
int T, K, N, DQ[NMAX], A[NMAX], S[NMAX], Total[NMAX];
int X[NMAX], Y[NMAX];
void read()
{
int i, j, k;
scanf("%d%d%d", &N, &K, &T);
for (i = 0; i < N; i++)
{
scanf("%d%d", &j, &k);
V.push_back(make_pair(k,j));
}
}
void solve()
{
int i, j;
V.push_back(make_pair(-1,0));
V.push_back(make_pair(NMAX,0));
sort(V.begin(), V.end());
for (i = 1; i <= N; i++) S[i] = S[i-1]+V[i].p;
for (i = 1; i <= K; i++)
X[i] = V[i].t, Y[i] = S[i];
for (i = K+1; i <= N; i++)
X[i] = V[i].t, Y[i] = S[i]-S[i-K];
for (i = 1; i <= N; i++) A[i] = S[i];
for (i = 1; i <= T; i++)
{
if (A[i]<A[i-1]) A[i] = A[i-1];
N%=1000;
for (j = 1; j <= N; j++)
if (i>=X[j])
if ((A[i-X[j]]+Y[j])>A[i])
A[i] = X[i-X[j]]+Y[j];
}
}
void write()
{
int i, max = 0;
for (i = 1; i <= T; i++)
if (max<A[i]) max = A[i];
printf("%d\n", max);
}
int main()
{
freopen("peste.in", "r", stdin);
freopen("peste.out", "w", stdout);
read();
solve();
write();
return 0;
}