Cod sursa(job #425511)

Utilizator vladiiIonescu Vlad vladii Data 25 martie 2010 20:20:19
Problema Lupul Urias si Rau Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.95 kb
#include <iostream>
#include <set>
using namespace std;

int N, X, L;
long long Tmax;
long long sol;
struct Oi {
    long long d, c;
} O[100005];
multiset<long long> Heap;
multiset<long long>::iterator it;

int cmp(Oi a, Oi b) {
    if(a.d!=b.d) return a.d>b.d;
}

int main() {
    FILE *f1=fopen("lupu.in", "r"), *f2=fopen("lupu.out", "w");
    int i, j, p, q;
    fscanf(f1, "%d %d %d", &N, &X, &L);
    for(i=1; i<=N; i++) {
         fscanf(f1, "%d %d", &p, &q);
         O[i].d=(X-p)/L+1; O[i].c=q;
         Tmax=max(Tmax, O[i].d);
    }
    sort(O+1, O+N+1, cmp);
    int pos=1;
    for(i=Tmax; i>=1; i--) {   
         while(O[pos].d==i) {
              Heap.insert(O[pos].c);
              pos++;
         }
         if(Heap.size()) {
              it=Heap.end(); it--;
              Heap.erase(it);
              sol+=(*it);
         }
    }
    fprintf(f2, "%lld\n", sol);
    fclose(f1); fclose(f2);
    return 0;
}