Cod sursa(job #163668)

Utilizator fireatmyselfBogdan-Alexandru Stoica fireatmyself 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;
}