Cod sursa(job #1854062)

Utilizator alexandra_udristoiuUdristoiu Alexandra Maria alexandra_udristoiu Data 22 ianuarie 2017 13:01:30
Problema Peste Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.54 kb
#include<fstream>
#include<algorithm>
#define f first
#define s second
#define DIM 50005
using namespace std;
int n, k, m, i, j, t, nr, sum;
int h[DIM], s[1005];
long long d[DIM], sol;
pair<int, int> v[DIM];
ifstream fin("peste.in");
ofstream fout("peste.out");
void upd(int poz){
    int c = poz, p = c / 2;
    while(p > 0 && v[ h[p] ].s > v[ h[c] ].s){
        swap(h[p], h[c]);
        c = p;
        p = c / 2;
    }
}
void elim(){
    int p = 1, c = 2;
    while(c <= nr){
        if(c + 1 <= nr && v[ h[c] ].s > v[ h[c + 1] ].s){
            c++;
        }
        if(v[ h[p] ].s > v[ h[c] ].s){
            swap(h[p], h[c]);;
            p = c;
            c = 2 * p;
        }
        else{
            break;
        }
    }
}
int main(){
    fin>> n >> k >> t;
    for(i = 1; i <= n; i++){
        fin>> v[i].s >> v[i].f;
        m = max(m, v[i].f);
    }
    sort(v + 1, v + n + 1);
    for(i = 1; i <= n; i++){
        j = i;
        while(v[i].f == v[j].f){
            nr++;
            h[nr] = j;
            sum += v[j].s;
            upd(nr);
            if(nr > k){
                sum -= v[ h[1] ].s;
                v[ h[1] ].s = 1000000000;
                elim();
                nr--;
            }
            j++;
        }
        s[ v[i].f ] = sum;
        i = j - 1;
    }
    for(i = 1; i <= t; i++){
        for(j = 1; j <= min(i, m); j++){
            d[i] = max(d[i], d[i - j] + s[j]);
        }
        sol = max(sol, d[i]);
    }
    fout<< d[t] <<"\n";
    return 0;
}