Pagini recente » Cod sursa (job #387700) | Cod sursa (job #804495) | Cod sursa (job #2878985) | Cod sursa (job #841376) | Cod sursa (job #61103)
Cod sursa(job #61103)
// 88 pcte
#include <stdio.h>
#include <vector>
#include <iterator>
#include <set>
using namespace std;
#define in "lupu.in"
#define out "lupu.out"
int val[100001], timp[100001];
struct Functor {
bool operator () (int i, int j)
{
return val[i] > val[j];
}
};
vector< vector<int> > ts;
multiset<int, Functor> s;
int n, d, t;
int main()
{
int tmax=0, x;
FILE *fin = fopen(in,"r");
char linie[101]; // nu o sa fie niciodata mai mare de 30 :P
freopen(out,"w",stdout);
fscanf(fin,"%d%d%d",&n,&t,&d);
fscanf(fin,"\n");
for ( int i = n; i > 0; --i )
{
// scanf("%d%d",&x,&val[i]);
int x=0;
int p=0;
int j=0;
fgets(linie,31,fin);
while ( linie[j] != ' ' )
{
x *= 10;
x += (int)linie[j]-48;
j++;
}
j++;
while ( linie[j] != '\n' )
{
p *= 10;
p += (int)linie[j]-48;
j++;
}
val[i] = p;
if ( x > t ) timp[i] = -1;
else
{
timp[i] = (t-x)/d;
}
if ( tmax < (t-x)/d ) tmax = (t-x)/d;
}
ts.resize(tmax+1);
for ( int i = n; i > 0; --i )
{
if ( timp[i] != -1 ) ts[timp[i]].push_back(i);
}
long long maxim=0;
for ( int j = tmax; j >= 0; --j )
{
if ( ts[j].size() != 0 )
{
for ( int i = ts[j].size()-1; i >= 0; --i )
{
s.insert(ts[j][i]);
}
}
maxim += val[*s.begin()];
s.erase(s.begin());
}
printf("%lld",maxim);
}