Pagini recente » Cod sursa (job #862429) | Cod sursa (job #2496245) | Cod sursa (job #1252694) | Cod sursa (job #229249) | Cod sursa (job #3192228)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#define MAXN 100000
#define DEBUG 0
#define PR(x) (x-1)/2
#define CH1(x) (x*2)+1
#define CH2(x) (x*2)+2
using namespace std;
vector<vector<int>> v;
int nrb = 0;
struct Option {
int x;
int id, pos;
};
Option hp[MAXN];
int hpl = 0;
void swap(int a, int b){
Option aux = hp[a];
hp[a] = hp[b];
hp[b] = aux;
}
void downheap(int x){
int chosen;
if(CH1(x) >= hpl)
return;
if(CH2(x) >= hpl || hp[CH2(x)].x > hp[CH1(x)].x){
chosen = CH1(x);
} else
chosen = CH2(x);
if(hp[x].x < hp[chosen].x){
swap(chosen, x);
downheap(chosen);
}
}
void upheap(int x){
if(x == 0)
return;
if(hp[x].x > hp[PR(x)].x){
swap(x, PR(x));
upheap(PR(x));
}
}
void remove(int x){
hpl --;
hp[x] = hp[hpl];
if(hpl > x)
downheap(x);
}
static inline int bracket(int x, int y){
if(x % y == 0)
return x / y;
return x / y + 1;
}
int main(){
int n, x, y;
ifstream fin ("lupu.in");
fin >> n >> x >> y;
nrb = bracket(x, y) + 1;
v.resize(nrb);
for(int i = 0; i < n; i ++){
int d, l;
fin >> d >> l;
v[bracket(d, y)].push_back(l);
}
fin.close();
for(int i = 0; i < nrb; i ++)
sort(v[i].begin(), v[i].end());
if(DEBUG){
for(int i = 0; i < nrb; i ++){
printf("%d: ", i);
for(int j = 0; j < (int)v[i].size(); j ++){
printf("%d ", v[i][j]);
}
printf("\n");
}
printf("\n");
}
int sum = 0;
for(int i = 0; i < nrb; i ++){
if(v[i].size() > 0){
Option o = {v[i][ v[i].size() - 1 ], i, (int)v[i].size() - 1};
hp[hpl] = o;
upheap(hpl);
hpl ++;
}
if(hpl > 0){
if(DEBUG)
cout << hp[0].x << " " << hp[0].id << " " << hp[0].pos << "\n";
sum += hp[0].x;
if(hp[0].pos != 0){
hp[0].pos --;
hp[0].x = v[hp[0].id][hp[0].pos];
downheap(0);
} else
remove(0);
}
}
ofstream fout ("lupu.out");
fout << sum << endl;
fout.close();
return 0;
}