Cod sursa(job #2627313)

Utilizator CraniXortDumitrescul Eduard CraniXort Data 10 iunie 2020 13:37:37
Problema Lupul Urias si Rau Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.98 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)
        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);
        ans += pq.top();
        pq.pop();

    }

    fout << ans << '\n';

    return 0;
}