Cod sursa(job #1994244)

Utilizator laurageorgescuLaura Georgescu laurageorgescu Data 24 iunie 2017 14:13:18
Problema Peste Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.09 kb
#include <fstream>
#include <algorithm>
#include <queue>

using namespace std;

ofstream fout ("peste.out");

class InputReader {
	public:
        InputReader() {}
        InputReader(const char *name) {
            fin = fopen(name, "r");
			buffpos = Size - 1;
        }
        inline InputReader &operator >>(int &n) {
			char ch = nextpos();
            while(ch < '0' || ch > '9') {
                ch = nextpos();
            }
            n = 0;
            while('0' <= ch && ch <= '9') {
                n = n * 10 + ch - '0';
                ch = nextpos();
            }
            return *this;
        }
    private:
        FILE *fin;
        static const int Size = 1 << 18;
        int buffpos;
        char buff[Size];

        inline char nextpos() {
            ++ buffpos;
            if(buffpos == Size) {
                buffpos = 0;
                fread(buff, Size, 1, fin);
            }
			return buff[ buffpos ];
        }
} fin ("peste.in");

const int nmax = 5e4;
const int tmax = 1000;
const int inf = 1 << 30;

long long p[tmax + 1], d[nmax + 1];
pair<int, int> v[nmax + 1];

priority_queue < int > h;

int main() {
    int n, k, ttotal;
    fin >> n >> k >> ttotal;

    int lim = 0;
    for (int i = 1; i <= n; ++ i) {
        int x, t;
        fin >> x >> t;
        v[ i ] = make_pair(t, x);
        lim = max(lim, t);
    }
    sort(v + 1, v + n + 1);

    int sum = 0, ind = 1;
    for (int i = 1; i <= tmax; ++ i) {
        while (ind <= n && v[ ind ].first <= i) {
            if ((int)h.size() < k) {
                sum += v[ ind ].second;

                h.push(-v[ ind ].second);
            } else if (v[ ind ].second > -h.top()) {
                sum += v[ ind ].second + h.top();
                h.pop();

                h.push(-v[ ind ].second);
            }

            ++ ind;
        }

        p[ i ] = sum;
    }

    d[ 0 ] = 0;
    for (int i = 1; i <= ttotal; ++ i) {
        d[ i ] = -inf;
        for (int j = 1; j <= lim && j <= i; ++ j) {
            d[ i ] = max(d[ i ], d[i - j] + p[ j ]);
        }
    }

    fout << d[ ttotal ] << "\n";

    fout.close();
    return 0;
}