Cod sursa(job #3359032)

Utilizator Andrei_GAndreiG Andrei_G Data 23 iunie 2026 01:15:56
Problema Lupul Urias si Rau Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.28 kb
#include <fstream>
#pragma GCC optimize("O3,unroll-loops")
#include <algorithm>
#include <cstring>
#include <climits>
#include <iomanip>
#include <numeric>
#include <bitset>
#include <string>
#include <vector>
#include <cmath>
#include <queue>
#include <deque>
#include <stack>
#include <list>
#include <map>
#include <set>
//#define int long long
//#define int short
#define pb push_back
#define f first
#define s second
using namespace std;

ifstream cin("lupu.in");
ofstream cout("lupu.out");

const int nmax = 1e5;

int n, x, l;

vector<int> wool[nmax + 5];

struct p{
    int d;
    int a;
}v[nmax + 5];

void fastio(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
}

void handleinput(){
    cin>>n>>x>>l;
    for (int i = 1; i <= n; i++){
        cin>>v[i].d>>v[i].a;
    }
}

bool cmp(p a, p b){
    return a.d < b.d;
}

void handleoutput(){
    int rez = 0, cnt = 0;
    for (int i = 1; i <= n; i++){
        v[i].d = (x - v[i].d) / l;
        v[i].d = min(v[i].d, n);
    }
    sort(v + 1, v + n + 1, cmp);
    for (int i = n; i >= 1; i--){
        if (v[i].d >= n){
            n--;
            rez += v[i].a;
        }
        else{
            break;
        }
    }
    for (int i = 1; i <= n; i++){
        int j = i;
        wool[v[i].d].push_back(v[i].a);
        while (j < n && v[j + 1].d == v[i].d){
            j++;
            wool[v[i].d].push_back(v[j].a);
        }
        sort(wool[v[i].d].begin(), wool[v[i].d].end());
        i = j;
    }
    priority_queue<int> pq;
    for (int i = v[n].d; i >= 0; i--){
        for (auto& i : wool[i]){
            pq.push(i);
        }
        if (!pq.empty()){
            rez += pq.top();
            pq.pop();
        }
    }
    cout<<rez;
}

signed main(){
    fastio();
    handleinput();
    handleoutput();
}

/*

10 6 2

0 16
0 7
1 14
1 3
1 16
1 10
1 18
1 16
2 13
3 7

------


10 6 2

0 16
1 18
1 16
2 13
2 15
2 7
3 0
4 19
4 7
4 14


pt fiecare d las max d + 1 wooluri si le pun intr-un array, sortandule
iterezi de la dmax la 1, pt fiecare:
    alegi max din elementele neluate pana atunci si elementlul max cu d = i
    pui elementele ramase cu d = i in pq


obs d >= n rezulta automat luam, stergem

*/