Pagini recente » Cod sursa (job #2422513) | Cod sursa (job #1882574) | Arhiva de probleme | Cod sursa (job #3359029) | Cod sursa (job #3359032)
#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
*/