Pagini recente » Statistici Lucia Negreanu-Maior (lnegreanu) | Cod sursa (job #1194789) | Cod sursa (job #2521568) | Cod sursa (job #2572840) | Cod sursa (job #436945)
Cod sursa(job #436945)
#include <stdio.h>
#include <stdlib.h>
#include <list>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
#define print_vector() \
for (itv = gutui_vector.begin(); itv != gutui_vector.end(); itv++) \
printf("(%d %d) ", (*itv).value, (*itv).time); \
printf("\n\n")
#define print_list() \
for (itl = gutui_list.begin(); itl != gutui_list.end(); itl++) \
printf("(%d %d) ", (*itl).value, (*itl).time); \
printf("\n\n")
typedef struct _gutuie_t {
int value;
int time;
} gutuie_t;
bool comparator(const gutuie_t &, const gutuie_t &);
int main(void) {
FILE *input = fopen("gutui.in", "r");
FILE *output;
int N, H, U;
int i, temp, j;
int sum = 0;
int max = 0;
gutuie_t gutuie;
vector<gutuie_t> gutui_vector;
vector<gutuie_t> :: iterator itv;
list<gutuie_t> gutui_list;
list<gutuie_t> :: iterator itl;
priority_queue<int> maxheap;
fscanf(input, "%d%d%d", &N, &H, &U);
gutui_vector.reserve(N);
gutui_list.clear();
for (i = 0; i < N; i++) {
fscanf(input, "%d%d", &temp, &gutuie.value);
if ((temp = H - temp) >= 0) {
gutuie.time = U != 0 ? temp / U : 0;
if (gutuie.time > max) max = gutuie.time;
gutui_vector.push_back(gutuie);
}
}
fclose(input);
N = gutui_vector.size();
sort(gutui_vector.begin(), gutui_vector.end(), comparator);
if (U != 0) N = H / U;
if (max < N) N = max;
for (itv = gutui_vector.begin(); itv != gutui_vector.end(); itv++)
gutui_list.push_back(*itv);
gutui_vector.clear();
for (i = N; i >= 0; i--) {
if (!gutui_list.empty()) {
for (j = 0; !gutui_list.empty() && gutui_list.front().time == i && j <= i; j++) {
maxheap.push(gutui_list.front().value);
gutui_list.pop_front();
}
while (!gutui_list.empty() && gutui_list.front().time == i)
gutui_list.pop_front();
}
if (!maxheap.empty()) {
sum += maxheap.top();
maxheap.pop();
}
}
gutui_list.clear();
output = fopen("gutui.out", "w");
fprintf(output, "%d\n", sum);
fclose(output);
return 0;
}
bool comparator(const gutuie_t &a, const gutuie_t &b) {
if (a.time > b.time)
return true;
if (a.time == b.time) {
if (a.value > b.value)
return true;
else
return false;
}
return false;
}