Pagini recente » Cod sursa (job #1897792) | Cod sursa (job #377879) | Cod sursa (job #726268) | Cod sursa (job #837980) | Cod sursa (job #2970570)
#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;
if (!stage)
{
long long total = 0;
for (int i = 1; i <= n; i++)
fin >> v[i].first >> v[i].second, total += (v[i].first <= bound ? v[i].second : 0);
fout << total;
return 0;
}
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)
{
bound -= stage;
int maxVal = -1;
while (k && v[k].first > bound)
{
if (used[k])
{
k--;
continue;
}
maxVal = max(maxVal, v[k--].second);
}
if (maxVal != -1)
total += maxVal;
else if (k)
{
used[poz[k]] = true;
total += maxi[k];
}
}
fout << total;
return 0;
}