Pagini recente » Cod sursa (job #1411177) | Cod sursa (job #2091399) | Cod sursa (job #1273686) | Cod sursa (job #1056981) | Cod sursa (job #2970561)
#include<bits/stdc++.h>
using namespace std;
ifstream fin("lupu.in");
ofstream fout("lupu.out");
int n, bound, stage;
pair <int, int> v[100001];
int maxi[100001], poz[100001];
bitset <100001> used;
int main()
{
fin >> n >> bound >> stage;
for (int i = 1; i <= n; i++)
fin >> v[i].first >> v[i].second;
sort(v + 1, v + n + 1);
maxi[0] = -1;
for (int i = 1; i <= n; i++)
if (v[i].first > maxi[i - 1])
maxi[i] = v[i].first, poz[i] = i;
else
maxi[i] = maxi[i - 1], poz[i] = poz[i - 1];
int k = n;
while (k && v[k].first > bound)
k--;
long long total = 0;
while (bound >= 0)
{
int maxVal = -1;
while (k && v[k].first > bound - stage)
{
if (used[k])
{
k--;
continue;
}
maxVal = max(maxVal, v[k--].second);
}
bound -= stage;
if (maxVal != -1)
total += maxVal;
else
{
used[poz[bound]] = true;
total += maxi[bound];
}
}
fout << total;
return 0;
}