Pagini recente » Cod sursa (job #821530) | Cod sursa (job #1092627) | Cod sursa (job #131201) | Cod sursa (job #154186) | Cod sursa (job #964310)
Cod sursa(job #964310)
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
vector < pair < int, int > > oi; //dist, lana
vector < pair < int, int > > rez; //lana, indicele
inline bool cmp (pair <int, int> a, pair <int, int> b){
return (a.first == b.first) ? (a.second > b.second) : (a.first > b.first);
}
int n, x, l, d;
long long sum;
int main(){
FILE *in = fopen("lupu.in", "r"), *out = fopen("lupu.out", "w");
if (in && out) {
int a, b, j;
fscanf(in, "%d %d %d\n", &n, &x, &l);
for (int i = 0; i < n; i++){
fscanf(in, "%d %d\n", &a, &b);
oi.push_back(pair<int,int>(a,b));
}
sort(oi.begin(), oi.end(), cmp);
a = oi[0].first;
rez.push_back(pair < int, int > (oi[0].second, 0));
for (int i = 1; i < n; i++){
if (oi[i].first != a) {
rez.push_back(pair < int, int > (oi[i].second,i));
sort(rez.begin(), rez.end());
j = rez.size()-1;
while(j >= 0 && oi[rez[j].second].first + d > x) j--;
if (j >= 0) {
sum += rez[j].first;
rez.erase(rez.begin()+j);
a = oi[i].first;
d += l;
}
}
else {
rez.push_back(pair < int, int > (oi[0].second,i));
}
}
sort(rez.begin(), rez.end());
for (j = rez.size()-1; j >= 0; j--){
if (oi[rez[j].second].first + d > x) continue;
sum += rez[j].first;
rez.erase(rez.begin()+j);
d += l;
}
fprintf(out, "%lld", sum);
fclose(in), fclose(out);
}
return 0;
}