Cod sursa(job #851110)

Utilizator stoicatheoFlirk Navok stoicatheo Data 9 ianuarie 2013 15:56:31
Problema Peste Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.46 kb
#include <cstdio>
#include <algorithm>
#include <set>
 
using namespace std;
 
#define MAX_N 100005
 
int N, K, T, Tmax;
long long B[MAX_N], R[MAX_N];
multiset <int> S;
 
struct peste
{
    int t, p;
} A[MAX_N];
 
struct cmp
{
    bool operator()(const peste &a, const peste &b)
    {
        return a.t < b.t;
    }
};
 
void citire()
{
    scanf("%d %d %d",&N, &K, &T);
     
    for(int i = 1; i <= N; ++i)
        scanf("%d %d",&A[i].p, &A[i].t);
     
    sort(A+1, A+N+1, cmp());
    Tmax = A[N].t + 1;
}
 
void pre()
{
    long long sum(0);
    for(int i = 1; i <= N; ++i)
    {
        if(S.size() < K)
        {
            S.insert(A[i].p);
            sum += A[i].p;
        }
         
        else
        {
            multiset <int> ::iterator it = S.begin();
            if(*it < A[i].p)
            {
                sum -= *it;
                S.erase(it);
                S.insert(A[i].p);
                sum += A[i].p;
            }
        }
        R[A[i].t] = sum;
    }
    for(int i = 0; i <= Tmax; ++i)
        R[i] = max(R[i], R[i-1]);
 
}
 
void solve()
{
    for(int i = 1; i <= T; ++i)
        for(int j = 1; j <= Tmax; ++j)
        {
            if(i < j) continue;
            B[i] = max(B[i], B[i-j] + R[j]);
        }
    printf("%lld\n",B[T]);
}
 
int main()
{
    freopen("peste.in","rt",stdin);
    freopen("peste.out","wt",stdout);
     
    citire();
    pre();
    solve();
}