Cod sursa(job #796185)

Utilizator vendettaSalajan Razvan vendetta Data 10 octombrie 2012 20:13:25
Problema Peste Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.59 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <set>
#include <queue>
#include <deque>

using namespace std;

ifstream f("peste.in");
ofstream g("peste.out");

#define nmax 50005
#define ll long long

int n, K, Ttotal, dp[nmax], cat[nmax];
pair<int, int> v[nmax];
multiset<int> S;

void citeste(){

	f >> n >> K >> Ttotal;
    for(int i=1; i<=n; ++i){
        int x, y;
        f >> x >> y;
        v[i] = make_pair(y,x);
    }
    sort(v+1, v+n+1);

}

void preprocesare(){

    //sunt sortate dupa timp; => o sa am nevoie pentru fiecare i de cele mai bune K produse
    int sum = 0;
    for(int i=1; i<=n; ++i){
        sum += v[i].second;//nr de pesti de la plsa i;
        S.insert(v[i].second);
        if (i > K){
            sum -= *S.begin();
            S.erase( S.begin() );
        }
        cat[i] = sum;
    }

}

void rezolva(){

    //fac un dp[i] = nr maxim de pesti pe care ii pot prinde daca ultima plasa o scot la momentul i
    //o sa mai am nevoie si de un cat[i] = X, cati pesti pot prinde daca scot plasa i(adica ea e cea mai mare();

    preprocesare();

    dp[0] = 0;
    for(int i=1; i<=Ttotal; ++i){
        int Max = 0;
        for(int j=1; j<=n && i>=v[j].first; ++j){
            if (i - v[j].first >= 0)
                Max = max(Max, dp[ i- v[j].first ] + cat[j]);
            else Max = max(Max, cat[j]);
        }
        dp[i] = max(dp[i-1],Max);
    }

    //cout << dp[Ttotal] << "\n";
    g << dp[Ttotal] << "\n";

}

int main(){

    citeste();
    rezolva();

    f.close();
    g.close();

    return 0;

}