Cod sursa(job #2361671)

Utilizator greelioGreenio Greely greelio Data 2 martie 2019 17:48:49
Problema Lupul Urias si Rau Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.21 kb
#include<bits/stdc++.h>
#define pii pair<long long,int>
#define x first
#define y second
#define ll long long
#define DIM 10000
char buff[DIM];
int poz=0;

void read(int &numar){
     numar = 0;
     while (buff[poz] < '0' || buff[poz] > '9')
          if (++poz == DIM)
               fread(buff,1,DIM,stdin),poz=0;
     while ('0'<=buff[poz] && buff[poz]<='9')
     {
          numar = numar*10 + buff[poz] - '0';
          if (++poz == DIM)
               fread(buff,1,DIM,stdin),poz=0;
     }
}
using namespace std;

const ll inf=1e9;
pair<int,int> a[100010];
set<pii>S;
int n,x,l;
ll rs;

int main() {
    freopen("lupu.in", "r", stdin);
    freopen("lupu.out", "w", stdout);
    read(n); read(x); read(l);
    for (int i=1; i<=n; ++i) {
        read(a[i].y); read(a[i].x);
        S.insert({0,i});
    }
    sort(a+1,a+1+n, greater<pair<int,int>>());
    for (int i=1; i<=n; ++i) {
        pii t=a[i];
        ll r=(x-t.y)/l+1;
        if (r<=0) continue;
        auto it=S.upper_bound({0,r});
        if (it==S.begin()) continue;
        else --it;
        if (it->x==inf) continue;
        ll y=it->y;
        rs+=t.x;
        S.erase(it);
    }
    cout<<rs;
    return 0;
}