Cod sursa(job #66941)

Utilizator raula_sanChis Raoul raula_san Data 21 iunie 2007 19:04:56
Problema Lupul Urias si Rau Scor 16
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.59 kb
#include <cstdio>
#include <queue>

#define MAX_N 100001

using namespace std;

long N, X, L, M;

long long unsigned SOL;

struct T
{
       long M, D, C;
} A[MAX_N];

class Compar
{
      public:
             bool operator()(T A, T B)
             {
                  return
                        A.M < B.M;
             }
};

priority_queue <T, vector <T>, Compar> H;

int main()
{
    FILE *f = fopen("lupu.in", "rt");
    FILE *g = fopen("lupu.out", "wt");

    long i, time, MAX;
    
    for(fscanf(f, "%ld %ld %ld", &N, &X, &L), i=1; i<=N; ++i)
    {
                  fscanf(f, "%ld %ld", &A[i].D, &A[i].C);
                  A[i].M = A[i].D > X ? -1 : (X - A[i].D) / L;

                  if(A[i].M != -1)
                  {
                            H.push(A[i]);
                            ++ M;
                  }
    }

    N = M;

    for(i=1; i<=N; ++i)
    {
             A[i] = H.top();
             H.pop();
    }

    priority_queue <long> Q;

    for(time=A[1].M, i=1; time>=0; --time)
    {
                     MAX = -1;
                     while(A[i].M == time)
                     {
                                  if(A[i].C > MAX) MAX = A[i].C;
                                  ++ i;
                     }
                     
                     if(MAX != -1) Q.push(MAX);
     
                     if(Q.empty() == true) break;
                     
                     SOL += Q.top();
                     Q.pop();
    }

    fprintf(g, "%llu", SOL);
    
    fclose(f);
    fclose(g);
    
    return 0;
}