Cod sursa(job #2839801)

Utilizator Albert_GAlbert G Albert_G Data 26 ianuarie 2022 16:44:38
Problema Lupul Urias si Rau Scor 100
Compilator cpp-64 Status done
Runda Teme Pregatire ACM Unibuc 2014, Anul I Marime 1.02 kb
#include <fstream>
#include <vector>
#include <algorithm>
#include <queue>

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

struct sheep{
    int distance, wool;
};

std::vector<sheep> s;
std::priority_queue<int, std::vector<int>, std::greater<int>> q;

int main(){
    int n, maxDist, leap;
    in >> n >> maxDist >> leap;
    for(int i=0; i<n; ++i){
        int d, w;
        in >> d >> w;
        s.push_back({d, w});
    }
    std::sort(s.begin(), s.end(), [](const sheep &a, const sheep &b){
        return a.distance > b.distance;
    });
    long long time = 0, woolQ = 0;
    for(int i=0; i<n; ++i){
        long long sheepDist = s[i].distance + time * leap;
        if(sheepDist <= maxDist){
            woolQ += s[i].wool;
            q.push(s[i].wool);
            ++time;
        }
        else if(!q.empty() && s[i].wool > q.top()){
                woolQ += s[i].wool - q.top();
                q.pop();
                q.push(s[i].wool);
        }
    }
    out << woolQ;
}