Cod sursa(job #796684)

Utilizator vendettaSalajan Razvan vendetta Data 12 octombrie 2012 09:20:46
Problema Peste Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.85 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 Tmax 1005
#define ll long long

int n, K, Ttotal;
ll dp[nmax], cat[Tmax];
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
    ll sum = 0LL;
    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 -= 1LL*(*S.begin());
            S.erase( S.begin() );
        }
        cat[v[i].first] = sum;//aici tin minte maximul pana la momentul v[i].first

    }

    for(int i=1; i<Tmax; ++i){
        cat[i] = max(cat[i], cat[i-1]);
    }

}

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();
    //schimb putin cand ma uit in spate ; T[i] <= 1000 => nu are rost sa ma duc printre toate cele n plase si ajunge printre
    //printre cele 1000
    preprocesare();

    dp[0] = 0LL;
    for(int i=1; i<=Ttotal; ++i){
        ll Max = 0;
        for(int j=0; j<Tmax && i>=j; ++j){
            Max = max(Max, dp[i-j] + 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;

}