Cod sursa(job #1848439)

Utilizator mariusn01Marius Nicoli mariusn01 Data 16 ianuarie 2017 00:42:01
Problema Peste Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.88 kb
#include <fstream>
#include <algorithm>
#define DIM 50010
#define p second
#define t first
#define INF 1000010
using namespace std;

class heap {
private:
    int H[51010];
    int n;
public:
    int top() {
        return H[1];
    }
    int size() {
        return n;
    }
    void push (int x) {
        H[++n] = x;
        int c = n;
        while (c > 1) {
            if (H[c] < H[c/2]) {
                swap(H[c], H[c/2]);
                c /= 2;
            } else
                break;
        }
    }
    void pop() {
        H[1] = H[n--];
        int p = 1, c = 2;
        while (c <= n) {
            if (c+1 <= n && H[c+1] < H[c])
                c++;
            if (H[p] > H[c]) {
                swap(H[p], H[c]);
                p = c;
                c *= 2;
            } else
                break;
        }
    }

};

heap s;

pair<int, int> v[DIM];
int x[DIM];
long long d[DIM];

int n, k, total, sum;

int main () {
    ifstream fin ("peste.in");
    ofstream fout("peste.out");
    fin>>n>>k>>total;
    for (int i=1;i<=n;i++) {
        fin>>v[i].second>>v[i].first;
    }
    sort(v+1, v+n+1);

    x[0] = -INF;
    int j = 1;
    for (int i = 1;i<=v[n].t;i++) {
        if (i < v[j].t) {
            x[i] = x[i-1];
        } else {
            while (j<=n && v[j].t == i) {
                s.push(v[j].p);
                sum += v[j].p;
                j++;
            }
            while (s.size() > k) {
                sum -= s.top();
                s.pop();
            }
            x[i] = sum;
        }
    }

    d[0] = 0;
    for (int i=1;i<=total;i++) {
        d[i] = -INF;
        for (int last = 1; i-last+1 >= 1 && last <= v[n].t; last++) {
            if (d[i-last] + x[last] > d[i])
                d[i] = d[i-last] + x[last];
        }
    }
    fout<<d[total];
    return 0;
}