Pagini recente » Cod sursa (job #2985983) | Cod sursa (job #75872) | Cod sursa (job #12876) | Algoritmiada 2015 - Clasament Runda 1, Juniori | Cod sursa (job #2034392)
#include <fstream>
#include <algorithm>
#include <set>
#define DIM 50002
using namespace std;
ifstream f("peste.in");
ofstream g("peste.out");
int n, k, T, val, d[DIM], s, maxim, kk, maximT;
struct plasa
{
int t, p;
} v[DIM], aux, folos[DIM];
bool cmp (plasa a, plasa b)
{
return a.t < b.t;
}
class compare
{
public:
bool operator() (plasa a, plasa b)
{
if(a.p == b.p)
return a.t < b.t;
return a.p > b.p;
}
};
multiset <plasa, compare> h;
multiset <plasa, compare>::iterator it;
int main()
{
f>>n>>k>>T;
for(int i = 1; i <= n; ++ i)
{
f>>v[i].p>>v[i].t;
if(v[i].t > maximT)
maximT = v[i].t;
}
sort(v + 1, v + n + 1, cmp);
int j = 1;
for(int i = 1; i <= maximT; ++ i)
{
for(; j <= n; ++ j)
{
if(v[j].t <= i)
h.insert(v[j]);
else
break;
}
s = 0;
maxim = 0;
if(!h.empty())
it = h.begin();
for(int l = 1; l <= k; ++ l)
{
if(!h.empty() && it != h.end())
{
aux = *it;
s += aux.p;
if(aux.t > maxim)
maxim = aux.t;
it++;
}
}
d[i] = s + d[i - maxim];
for(int l = 1; l <= i / 2; ++ l)
{
d[i] = max(d[i], d[l] + d[i - l]);
}
}
for(int i = maximT; i <= T; ++ i)
{
for(int j = 1; j <= i / 2; ++ j)
{
d[i] = max(d[i], d[j] + d[i - j]);
}
}
maxim = 0;
for(int i = 1; i <= T; ++ i)
if(d[i] > maxim)
maxim = d[i];
g<<maxim;
return 0;
}