Cod sursa(job #1867799)

Utilizator alexpetrescuAlexandru Petrescu alexpetrescu Data 4 februarie 2017 12:47:27
Problema Peste Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.99 kb
#include <cstdio>
#include <queue>
#include <algorithm>

#define MAXG 50000
#define MAXT 1000

std::priority_queue <int, std::vector <int>, std::greater <int> > q;
std::vector <int> v[MAXT+1];
long long d[MAXG+1];

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

    int n, k, g;
    fscanf(fin, "%d%d%d", &n, &k, &g);

    for(int i=1; i<=n; i++){
        int x, y;
        fscanf(fin, "%d%d", &x, &y);
        v[y].push_back(x);
    }

    long long sum=0;
    for(int i=1; i<=MAXT; i++){
        for(auto x:v[i]){
            if(k>(int)q.size()){
                sum+=x;
                q.push(x);
            }else if(x>q.top()){
                sum+=x-q.top();
                q.pop();
                q.push(x);
            }
        }
        for(int j=i; j<=g; j++)
            d[j]=std::max(d[j], d[j-i]+sum);
    }

    fprintf(fout, "%lld\n", d[g]);

    fclose(fin);
    fclose(fout);
    return 0;
}