Cod sursa(job #1384474)

Utilizator alexandra_udristoiuUdristoiu Alexandra Maria alexandra_udristoiu Data 11 martie 2015 09:41:14
Problema Lupul Urias si Rau Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.28 kb
#include<fstream>
#include<algorithm>
using namespace std;
int n, i, j, nr, p, c, maxim, L, x;
long long sum;
pair<int, int> v[100003], w[100003], aux;
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;
		if(v[i].first <= x){
			v[i].first = (x - v[i].first) / L;
			if(v[i].first > maxim){
				maxim = v[i].first;
			}
		}
		else{
			v[i].first = -1000000;
		}
	}
	sort(v + 1, v + n + 1, cmp);
	i = 0;
	nr = 0;
	for(j = maxim; j >= 0; 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){
					aux = w[p];
					w[p] = w[c];
					w[c] = aux;
					c = p;
					p = c / 2;
				}
				else{
					break;
				}
			}
		}
		if(nr != 0){
			sum += w[1].second;
			w[1] = w[nr];
			nr--;
			p = 1;
			c = 2;
			while(c <= nr){
				if(c + 1 <= nr && w[c+1].second > w[c].second){
					c++;
				}
				if(w[c].second > w[p].second){
					aux = w[p];
					w[p] = w[c];
					w[c] = aux;
					p = c;
					c = p * 2;
				}
				else{
					break;
				}
			}
		}
	}
	fout<< sum <<"\n";
	return 0;
}