Pagini recente » Cod sursa (job #1028180) | Cod sursa (job #3149457) | Cod sursa (job #3299192) | Cod sursa (job #3293726) | Cod sursa (job #3298863)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("lupu.in");
ofstream fout("lupu.out");
template<typename T>
class priorityQueue
{
private:
vector<T> a;
static inline int parent(int p)
{
return (p - 1) / 2;
}
static inline int leftChild(int p)
{
return (2 * p + 1);
}
static inline int rightChild(int p)
{
return (2 * p + 2);
}
void shiftUp(int p)
{
while(p > 0)
{
int t = parent(p);
if(a[p] <= a[t]) return;
swap(a[p], a[t]);
p = t;
}
}
void shiftDown(int p)
{
int n = a.size();
while (p < n / 2)
{
int maxim = p;
int left = leftChild(p);
int right = rightChild(p);
if(left < n && a[maxim] < a[left])
maxim = left;
if(right < n && a[maxim] < a[right])
maxim = right;
if(maxim == p) return;
swap(a[maxim], a[p]);
p = maxim;
}
}
public:
priorityQueue() = default;
~priorityQueue() = default;
bool Empty(){ return a.empty(); }
int Size(){ return a.size(); }
void Push(const T& val)
{
a.push_back(val);
shiftUp(a.size() - 1);
}
void Pop()
{
if(Empty()) return;
a[0] = a.back();
a.pop_back();
if(!a.empty()) shiftDown(0);
}
const T& Top()
{
if(!Empty()) return a[0];
}
void ChangePriority(const T& oldVal, const T& newVal)
{
int poz = -1;
for(int i = 0; i < a.size(); i++)
if(a[i] == oldVal)
{
poz = i;
break;
}
if(poz == -1) return;
a[poz] = newVal;
if(a[poz] > oldVal) shiftDown(poz);
else shiftUp(poz);
}
};
/// arme1 - pbinfo
void prob1()
{
int n,m, i, x;
priorityQueue<long long> q;
long long s = 0;
cin >> n >> m;
for(i = 1; i <= n; i++)
{
cin >> x;
q.Push(x);
}
for(i = 1; i <= m; i++)
{
cin >> x;
q.Push(x);
}
while(n != 0)
{
s += q.Top();
q.Pop();
n--;
}
cout << s;
}
/// Lupul urias si rau - infoarena
bool comp(pair<int, int> a, pair<int, int> b)
{
return a.first < b.first;
}
void prob2()
{
int n = 0, x = 0, l = 0, i, dist = 0;
unsigned long long ans = 0;
vector<pair<int, int> > o;
priorityQueue<int> q;
fin >> n >> x >> l;
for(i = 1; i <= n; ++i)
{
int d, lana;
fin >> d >> lana;
o.push_back({d, lana});
}
sort(o.begin(), o.end(), comp);
for(i = 0; i < n; ++i)
{
if(dist >= o[i].first) q.Push(o[i].second);
else
{
if(!q.Empty())
{
ans += q.Top();
q.Pop();
}
dist += l;
--i;
if(dist > x) break;
}
}
while(!q.Empty() && dist <= x)
{
ans += q.Top();
q.Pop();
dist += l;
}
fout << ans;
}
int main()
{
prob2();
return 0;
}