Cod sursa(job #2627321)

Utilizator CraniXortDumitrescul Eduard CraniXort Data 10 iunie 2020 13:43:17
Problema Lupul Urias si Rau Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.15 kb
#include <bits/stdc++.h>
#define maxn 100005

std::ifstream fin ("lupu.in");
std::ofstream fout ("lupu.out");

struct Sheep{
    long long dist, val;
}sheep[maxn];

bool sheepSort (Sheep a, Sheep b){
    return a.dist > b.dist;
}

int main()
{
    long long n, maxDist, moveDist, i, k;
    long long ans=0;
    fin >> n >> maxDist >> moveDist;

    for (i=0; i<n; i++){
        fin >> sheep[i].dist >> sheep[i].val;
        if (moveDist){
            if (maxDist < sheep[i].dist)
                sheep[i].dist = -1;
            else
                sheep[i].dist = (maxDist - sheep[i].dist) / moveDist;
        }

    }

    if (moveDist == 0){
        for (i=0; i<n; i++)
            ans += sheep[i].val;
        fout << ans << '\n';
        return 0;
    }


    std::sort (sheep, sheep+n, sheepSort);

std::priority_queue <long long> pq;
    for (i=0, k=maxDist/moveDist; k>=0; k--){

        for (;i<n and sheep[i].dist == k; i++)
            pq.push (sheep[i].val);
        if (pq.empty() == false){
            ans += pq.top();
            pq.pop();
        }


    }

    fout << ans << '\n';

    return 0;
}