Cod sursa(job #3171598)

Utilizator KarinaDKarina Dumitrescu KarinaD Data 19 noiembrie 2023 03:07:00
Problema Lupul Urias si Rau Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.96 kb
#include <iostream>
#include <fstream>
#include <queue>
#include <algorithm>

using namespace std;

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

const long long N = 2e5;

struct oaie{
    int wool, dist;
} v[N];

priority_queue <int> pq;

bool cmp ( oaie x, oaie y ) {
    
    if ( x.dist != y.dist )
        return ( x.dist < y.dist );
    else
        return ( x.wool < y.wool );
}

int main() {
    
    int n, x, l, d;
    
    fin >> n >> x >> l;
    
    for ( int i = 1; i <= n; i++ ) {
        fin >> d >> v[i].wool;
        v[i].dist = (x - d) / l;
    }
    
    sort ( v + 1, v + n + 1, cmp );
    
    
    int k = n;
    long long ans = 0;
    
    for ( int i = v[n].dist; i >= 0; i-- ) {
        
        while( k > 0 && v[k].dist >= i ){
            pq.push ( v[k].wool );
            k--;
        }
        
        if( pq.size() > 0 ) {
            ans = ans + pq.top();
            pq.pop();
        }
    }
    
    fout << ans;
    
    return 0;
}