Cod sursa(job #796685)

Utilizator vendettaSalajan Razvan vendetta Data 12 octombrie 2012 09:25:05
Problema Peste Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.19 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
#define Cifmax 5000005
int n, K, Ttotal;
ll dp[nmax], cat[Tmax];
pair<int, int> v[nmax];
multiset<int> Heap;
int poz;
char S[Cifmax];

void buf( int &nr){

    nr = 0;
    for(; S[poz]<'0' || S[poz]>'9'; poz++);
    for(; S[poz]>='0' && S[poz]<='9'; poz++){
        nr = nr * 10 + (S[poz] - '0');
    }

}

void citeste(){

    f.getline(S, Cifmax, EOF);

	//f >> n >> K >> Ttotal;
    buf(n); buf(K); buf(Ttotal);

    for(int i=1; i<=n; ++i){
        int x, y;
        //f >> x >> y;
        buf(x); buf(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;
        Heap.insert(v[i].second);
        if (i > K){
            sum -= 1LL*(*Heap.begin());
            Heap.erase( Heap.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;

}