Cod sursa(job #1849081)

Utilizator mariusn01Marius Nicoli mariusn01 Data 16 ianuarie 2017 23:35:54
Problema Peste Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.81 kb
#include <cstdio>
#include <algorithm>
#include <queue>
#define DIM 50010
#define p second
#define t first
#define INF 1000010
#define DIMBUFF 100000
using namespace std;

FILE *fin  = fopen("peste.in", "r");
FILE *fout = fopen("peste.out", "w");

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>>1]) {
                swap(H[c], H[c>>1]);
                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 <<= 1;
            } else
                break;
        }
    }

};


struct pereche {
    int t;
    int p;
} v[DIM];


int cmp(const pereche &a, const pereche &b) {
    if(a.first == b.first)
        return a.second < b.second;
    else
        return a.first < b.first;
}

char buff[DIMBUFF];
int pp;

int numar() {
    int val = 0;
    while (!(buff[pp] >= '0' && buff[pp] <= '9')) {
        pp++;
        if (pp == DIMBUFF) {
            fread(buff, 1, DIMBUFF, fin);
            pp=0;
        }

    }
    while (buff[pp] >= '0' && buff[pp] <= '9') {
        val = val*10 + buff[pp] - '0';
        pp++;
        if (pp == DIMBUFF) {
            fread(buff, 1, DIMBUFF, fin);
            pp=0;
        }
    }
    return val;
}

int main () {

    int x[DIM];
    long long d[DIM];

    int n, k, total, sum=0;

    //heap s;
    priority_queue<int,vector<int>,greater<int> > s;


//    fin>>n>>k>>total;
    n = numar();
    k = numar();
    total = numar();
    for (int i=1;i<=n;i++) {
        //fin>>v[i].p>>v[i].t;
        v[i].p = numar();
        v[i].t = numar();
    }
    sort(v+1, v+n+1, cmp);

    x[0] = -INF;
    int j = 1;
    for (int i = 1;i<=n;i++) {
        s.push(v[i].p);
        sum += v[i].p;

        if (s.size() > k) {
            sum -= s.top();
            s.pop();
        }
        x[v[i].t] = sum;
    }


    d[0] = 0;
    int m = v[n].t, last;
    //x[0] = 0;
    for (int i=1;i<=m;i++)
        x[i] = max(x[i], x[i-1]);

    for (int i=1;i<=m;++i) {
        d[i] = 0;
        for (last = 1; last<=i; ++last) {
            d[i] = max(d[i], d[i-last] + x[last]);
        }
    }

    for (int i=m+1;i<=total;++i) {
        d[i] = 0;
        for (last = 1; last<=m; ++last) {
            d[i] = max(d[i], d[i-last] + x[last]);
        }
    }
    fprintf(fout, "%lld\n", d[total]);

    return 0;
}