Cod sursa(job #1264715)

Utilizator tavi.belu1994FMI Belu Andrei Octavian tavi.belu1994 Data 16 noiembrie 2014 02:01:23
Problema Lupul Urias si Rau Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.21 kb
#include <iostream>
#include <cstdio>       // fscanf
#include <algorithm>    // std::sort
#include <vector>       // std::vector
#include <queue>
using namespace std;
FILE *f,*g;

class Sheep {
public:
    int dist;
    int wool;
    int pas;
}sh[100001];

bool cmp (Sheep i,Sheep j) { return (i.pas < j.pas); }

int main()
{
    f = fopen("lupu.in","r");
    g = fopen("lupu.out","w");
    int N,X,L,NOK;
    NOK = 0;
    fscanf(f,"%d %d %d", &N, &X, &L);
    for(int it = 0 ; it < N ; it ++){
        int auxd, auxw;
        fscanf(f,"%d %d",&auxd,&auxw);
        if(auxd <= X){
            sh[NOK].dist = auxd;
            sh[NOK].wool = auxw;
            sh[NOK].pas = (X - auxd) / L;
            NOK++;
        }
    }
    std::sort (sh, sh + NOK, cmp);

    int pasmax = sh[NOK - 1].pas;
    int crt = NOK - 1;
    long long sol = 0;

    priority_queue < int > myqueue;

    for(int it = pasmax; it >= 0; it--) {
        while(sh[crt].pas == it) {
            myqueue.push(sh[crt].wool);
            crt --;
        }
        if(!myqueue.empty()) {
            sol += myqueue.top();
            myqueue.pop();
        }
    }

    fprintf(g, "%lld", sol);

    return 0;
}