Cod sursa(job #2504983)

Utilizator AlexPascu007Pascu Ionut Alexandru AlexPascu007 Data 5 decembrie 2019 21:58:16
Problema Lupul Urias si Rau Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.19 kb
#include <bits/stdc++.h>
#define DIM 100010
using namespace std;
ifstream fin("lupu.in");
ofstream fout("lupu.out");
long long n,i,x,l,sol,tmax,d,j;
struct oaie{
    long long lana,pas;
    bool operator<(const oaie &other) const { //am stat 1 ora sa caut cum fac operator de comparare
        if (lana==other.lana)                 //pe structuri
            return pas>other.pas;
        return lana<other.lana;
    }
};
vector<oaie> v[DIM];
oaie a,last;
priority_queue<oaie> q;
int main() {
    fin>>n>>x>>l;
    //calculam nr maxim de pasi dupa care poate ajunge lupul la o oaie
    //si punem toate oile cu un anumit nr de pasi intr-un vector
    for (i=1;i<=n;i++) {
        fin>>d>>a.lana;
        if (x>d) {
            a.pas=(x-d)/l+1;
            tmax=max(a.pas,tmax);
            v[a.pas].push_back(a);
        }
    }
    //metoda greedy->la fiecare pas de la tmax la 1 punem oile din v[pas] intr-un priority queue
    //si extragem maximul din pq
    for (i=tmax;i>=1;i--) {
        for (j=0;j<v[i].size();j++)
            q.push(v[i][j]);
        if (!q.empty()) {
            sol+=q.top().lana;
            q.pop();
        }
    }
    fout<<sol;
    return 0;
}