Cod sursa(job #1258127)

Utilizator jul123Iulia Duta jul123 Data 8 noiembrie 2014 15:07:59
Problema Lupul Urias si Rau Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.93 kb
#include<iostream>
#include<cstdio>
#include<queue>
#include<algorithm>

#define MAX_N 100005

using namespace std;

typedef struct o_oaie {
    int d;
    int a;
    int t;
}oaie;

oaie o[MAX_N];

priority_queue<int> myq;

bool cmp(oaie c, oaie b) {
    return c.t < b.t;
}

int main()
{
    FILE *fin = fopen("lupu.in", "r");
    FILE *fout = fopen("lupu.out", "w");

    int n, x, l;
    fscanf(fin, "%d %d %d", &n, &x, &l);

    for(int i = 0; i < n; ++i) {
        fscanf(fin, "%d %d", &o[i].d, &o[i].a);
        o[i].t = (x - o[i].d)/l;
    }

    sort(o, o + n, cmp);

    int tmax = o[n - 1].t;
    int crt = n - 1;
    int s = 0;

    for(int i = tmax; i >= 0; --i) {
        while(o[crt].t == i) {
            myq.push(o[crt].a);
            --crt;
        }
        if(!myq.empty()) {
            s += myq.top();
            myq.pop();
        }
    }

    fprintf(fout, "%d", s);
}