Cod sursa(job #851112)

Utilizator stoicatheoFlirk Navok stoicatheo Data 9 ianuarie 2013 15:57:20
Problema Peste Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.42 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);
 
}
 
struct cmp{
 
    bool operator() (const int &A, const int &B){
 
        return A > B;
 
    }
 
};
 
void preprocesare(){
 
    priority_queue< int, vector<int>, cmp> Q;
 
    //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);
        Q.push(v[i].second);
        if (i > K){
            sum -= 1LL*(Q.top());
            //Heap.erase( Heap.begin() );
            Q.pop();
        }
        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;
 
}