Cod sursa(job #346425)

Utilizator vladiiIonescu Vlad vladii Data 7 septembrie 2009 19:29:34
Problema Lupul Urias si Rau Scor 16
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.14 kb
#include <stdio.h>
using namespace std;
int elem=0, heap[100000];
void addheap(int lana);
void delheap(int i);
int main() {
    int n, x, l, lung[100000], lana[100000], suma=0, i, j, pas, t;
    FILE *in = fopen("lupu.in", "r"), *out = fopen("lupu.out", "w");
    fscanf(in, "%d%d%d", &n, &x, &l);
    for(i=1; i<=n; i++) {
             fscanf(in, "%d%d", &lung[i], &lana[i]);
    }
    /*for(i=1; i<=n; i++) {
             printf("%d\n", heap[i][0]);
    }*/
    //am construit heapul.
    pas=n; t=1;
    while(pas>0) {
             for(i=1; i<=n; i++) {
                          if(lung[i]+t*l>x) {
                               pas--; addheap(lana[i]);
                               lung[i]=-1000;
                      }
             } t++;
             //printf("%d %d\n", heap[1], pas);
             suma+=heap[1]; elem=0;
    }
    fprintf(out, "%d", suma);
    fclose(in); fclose(out);
    return 0;         
}

void addheap(int lana) {
     int s, k;
     elem++;
     heap[elem]=lana;
     s=elem;
     if(s==1) { return; }
     while(s>1 && heap[s]>heap[(int)s/2]) {
          k=heap[s];
          heap[s]=heap[(int)s/2];
          heap[(int)s/2]=k;
          s=(int)s/2;
     }
}

/*
void delheap(int i) {
     int s, k, w;
     heap[i][0]=heap[elem][0];
     heap[i][1]=heap[elem][1];
     elem--;
     s=i;
     if(heap[s][0]>heap[(int)s/2][0]) {
        while(s && heap[s][0]>heap[(int)s/2][0]) {
          k=heap[s][0];
          heap[s][0]=heap[(int)s/2][0];
          heap[(int)s/2][0]=k;
          k=heap[s][1];
          heap[s][1]=heap[(int)s/2][1];
          heap[(int)s/2][1]=k;
          s=(int)s/2;
        }
     }
     else {
          w=s*2;
          while(w<elem) {
                if(w+1<elem && heap[w+1][0]>heap[w][0]) { w++; }
                if(heap[s][0]==heap[w][0]) { return; }
                k=heap[s][0];
                heap[s][0]=heap[w][0];
                heap[w][0]=k;
                k=heap[s][1];
                heap[s][1]=heap[w][1];
                heap[w][1]=k;
                s=w;
                w=w*2;
          }
     }                          
}
*/