Pagini recente » Monitorul de evaluare | Cod sursa (job #2473364) | Monitorul de evaluare | Cod sursa (job #822043) | Cod sursa (job #2464843)
#include <fstream>
#include <map>
#include <queue>
#include <vector>
#include <algorithm>
#include <cmath>
#define d first
#define a second
using namespace std;
ifstream f("lupu.in");
ofstream g("lupu.out");
const int NMAX = 1e5 + 50;
int N, X, L;
long long ans = 0;
pair < int, int > A[NMAX];
int Time[NMAX];
map < int, vector < int > > mp;
vector < int > Keys;
priority_queue < long long > Q;
static inline int Max_Moment (int Val)
{
if(Val > X)
return 0;
return 1LL * (1LL * (X - Val) / L + 1LL);
}
static inline void SpecialCase ()
{
for(int i = 1; i <= N; ++i)
{
f >> A[i].d >> A[i].a;
if(A[i].d <= X)
ans += 1LL * A[i].a;
}
g << ans << '\n';
return;
}
static inline void Read ()
{
f.tie(NULL);
f >> N >> X >> L;
if(L == 0)
{
SpecialCase();
exit(0);
}
for(int i = 1; i <= N; ++i)
{
f >> A[i].d >> A[i].a;
Time[i] = Max_Moment(A[i].d);
if(Time[i] == 0)
continue;
mp[Time[i]].push_back(A[i].a);
}
return;
}
static inline bool cmp (int a, int b)
{
return (a > b);
}
int main()
{
Read();
int Last = 0, i = 0;
for(auto it : mp)
Keys.push_back(it.first);
sort(Keys.begin(), Keys.end(), cmp);
if(Keys[(int)Keys.size() - 1] != 1)
Keys.push_back(1);
for(auto it : Keys)
{
if(i == 0)
{
Last = it;
for(auto j : mp[it])
Q.push(j);
if(!Q.empty())
{
ans += 1LL * Q.top();
Q.pop();
}
}
else
{
if(Last - 1 >= it + 1 && !Q.empty())
{
for(int i = Last - 1; i >= it + 1 && !Q.empty(); --i)
{
ans += 1LL * Q.top();
Q.pop();
}
}
for(auto j : mp[it])
Q.push(j);
if(!Q.empty())
{
ans += 1LL * Q.top();
Q.pop();
}
Last = it;
}
++i;
}
g << ans << '\n';
return 0;
}