Cod sursa(job #1384189)

Utilizator alexandra_udristoiuUdristoiu Alexandra Maria alexandra_udristoiu Data 10 martie 2015 22:22:46
Problema Lupul Urias si Rau Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.1 kb
#include<fstream>
#include<algorithm>
using namespace std;
int n, i, j, nr, p, c, sum, maxim, L, x;
pair<int, int> v[100003], w[100003];
ifstream fin("lupu.in");
ofstream fout("lupu.out");
int cmp(pair<int, int> a, pair<int, int> b){
	return a.first > b.first;
}
int main(){
	fin>> n >> x >> L;
	for(i = 1; i <= n; i++){
		fin>> v[i].first >> v[i].second;
		v[i].first = (x - v[i].first) / L + 1;
		if(v[i].first > maxim){
			maxim = v[i].first;
		}
 	}
	sort(v + 1, v + n + 1, cmp);
	i = 0;
	nr = 0;
	for(j = maxim; j >= 1; j--){
		while(v[i+1].first == j){
			i++;
			nr++;
			w[nr] = v[i];
			c = nr;
			p = nr / 2;
			while(p > 0){
				if(w[p].second < w[c].second){
					swap(w[p], w[c]);
					c = p;
					p = c / 2;
				}
				else{
					break;
				}
			}
		}
		sum += w[1].second;
		w[1] = w[nr];
		nr--;
		p = 1;
		c = 2;
		while(c <= nr){
			if(c + 1 <= nr && v[c+1].second > v[c].second){
				c++;
			}
			if(w[p].second < w[c].second){
				swap(w[p], w[c]);
				p = c;
				c = p * 2;
			}
			else{
				break;
			}
		}
	}
	fout<< sum <<"\n";
	return 0;
}