Pagini recente » Cod sursa (job #2091867) | Cod sursa (job #1795885) | Cod sursa (job #2945836) | Cod sursa (job #456961) | Cod sursa (job #2551962)
#include <fstream>
#include <iomanip>
#include <string>
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <math.h>
#include <set>
#include <map>
#include <string.h>
#include <queue>
#include <stack>
#define INF 0x3f3f3f3f
using namespace std;
#ifdef DEBUG
string name = "data";
#else
string name = "lupu";
#endif
ifstream fin(name + ".in");
ofstream fout(name + ".out");
#define MAXN 100005
int n, k, l;
int nxt[MAXN];
struct Item {
int d;
int v;
};
bool canInsert(int x) {
if (x == 0) {
return false;
}
if (nxt[x] == x) {
return true;
}
return canInsert(nxt[x]);
}
void insert(int x) {
int y = nxt[x - 1];
while (nxt[y] != y) {
y = nxt[y];
}
nxt[x] = y;
}
int main() {
auto compare = [](Item lhs, Item rhs) {
if (lhs.v == rhs.v) {
return lhs.d < rhs.d;
}
return lhs.v < rhs.v;
};
priority_queue<Item, vector<Item>, decltype(compare)> pq(compare);
fin >> n >> k >> l;
for (int i = 1; i <= n; ++i) {
nxt[i] = i;
int d, v;
fin >> d >> v;
pq.push({d,v});
}
int64_t sol = 0;
while (!pq.empty()) {
auto x = pq.top();
pq.pop();
int maxT = (k - x.d) / l + 1;
if (canInsert(maxT)) {
insert(maxT);
sol += x.v;
}
}
fout << sol;
return 0;
}