Cod sursa(job #2551974)

Utilizator memecoinMeme Coin memecoin Data 20 februarie 2020 14:10:32
Problema Lupul Urias si Rau Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.47 kb
#include <fstream>
#include <iomanip>
#include <string>
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <math.h>
#include <set>
#include <map>
#include <string.h>
#include <queue>
#include <stack>

#define INF 0x3f3f3f3f

using namespace std;

#ifdef DEBUG
string name = "data";
#else
string name = "lupu";
#endif

ifstream fin(name + ".in");
ofstream fout(name + ".out");

#define MAXN 100005

int n, k, l;

int nxt[MAXN];

struct Item {
    int d;
    int v;
};

int canInsert(int x) {
    if (x == 0) {
        return 0;
    }
    
    if (nxt[x] == x) {
        return x;
    }
    
    int res = canInsert(nxt[x]);
    
    nxt[x] = res;
    
    return res;
}

void insert(int x) {
    nxt[x] = nxt[x - 1];
}

int main() {
    
    auto compare = [](Item lhs, Item rhs) {
        if (lhs.v == rhs.v) {
            return lhs.d < rhs.d;
        }
        
        return lhs.v < rhs.v;
    };
    
    priority_queue<Item, vector<Item>, decltype(compare)> pq(compare);
    
    fin >> n >> k >> l;
    
    for (int i = 1; i <= n; ++i) {
        nxt[i] = i;
        
        int d, v;
        fin >> d >> v;
        
        pq.push({d,v});
    }
    
    int64_t sol = 0;
    
    while (!pq.empty()) {
        auto x = pq.top();
        pq.pop();
        
        int maxT = (k - x.d) / l + 1;
    
        int node = canInsert(maxT);
        
        if (node != 0) {
            insert(node);
            sol += x.v;
        }
    }
    
    fout << sol;
    
    return 0;
}