Cod sursa(job #1546468)

Utilizator cristinabCristina Brinza cristinab Data 8 decembrie 2015 03:25:44
Problema Lupul Urias si Rau Scor 92
Compilator java Status done
Runda Arhiva de probleme Marime 3.22 kb
//package lupul.urias.si.rau;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;

class Heap {
	int currentPosition;
	int[] heap;
	// default comparator - max-heap
	Comparator<Integer> comparator = new Comparator<Integer>() {
		public int compare(Integer i1, Integer i2) {
			return i1.compareTo(i2);
		}
	};

	public Heap(int n) {
		heap = new int[n + 1];
		currentPosition = 0;
	}

	public Heap(int n, Comparator<Integer> comparator) {
		this(n);
		this.comparator = comparator;
	}

	private void swap(int i, int j) {
		int aux = heap[i];
		heap[i] = heap[j];
		heap[j] = aux;
	}

	public void add(int x) {
		heap[++currentPosition] = x;
		int k = currentPosition;

		while (k > 1 && comparator.compare(heap[k], heap[k / 2]) > 0) {
			swap(k / 2, k);
			k = k / 2;
		}
	}

	private void heapify(int i) {
		int k = i;
		int left = 2 * k;
		int right = 2 * k + 1;
		int index = k;

		if (left <= currentPosition && comparator.compare(heap[left], heap[k]) > 0) {
			index = left;
		}

		if (right <= currentPosition && comparator.compare(heap[right], heap[index]) > 0) {
			index = right;
		}

		if (index != k) {
			swap(index, k);
			heapify(index);
		}

	}

	public int remove() {
		if (currentPosition >= 1) {

			int removed = heap[1];
			heap[1] = heap[currentPosition--];

			heapify(1);

			return removed;
		}
		
		return 0;
	}
}

class Main {

	static HashMap<Integer, ArrayList<Integer>> times = new HashMap<Integer, ArrayList<Integer>>();
	static int maxT;

	private static BigInteger wolfSolve(int N) {
		Heap heap = new Heap(N);
		BigInteger sum = new BigInteger("0");

		for (int i = maxT; i >= 1; i--) {
			ArrayList<Integer> sheeps = times.get(i);

			if (sheeps != null) {
				for (int sheep : sheeps) {
					heap.add(sheep);
				}
			}
			
			sum = sum.add(new BigInteger(heap.remove() + ""));
		}

		return sum;
	}

	public static void main(String[] args) {
		try {
			BufferedReader br = new BufferedReader(new FileReader("lupu.in"));
			BufferedWriter bw = new BufferedWriter(new FileWriter("lupu.out"));

			String firstLine = br.readLine();
			String[] firstLineSplit = firstLine.split(" ");
			int N = Integer.parseInt(firstLineSplit[0]);
			int X = Integer.parseInt(firstLineSplit[1]);
			int L = Integer.parseInt(firstLineSplit[2]);
			maxT = -Integer.MAX_VALUE;

			for (int i = 0; i < N; i++) {
				String line = br.readLine();
				String[] lineSplit = line.split(" ");

				int distance = Integer.parseInt(lineSplit[0]);
				int wool = Integer.parseInt(lineSplit[1]);

				int maxTimeChooseI = (X - distance) / L + 1;

				ArrayList<Integer> sheeps = times.get(maxTimeChooseI);
				if (sheeps == null) {
					sheeps = new ArrayList<Integer>();
				}
				sheeps.add(wool);

				times.put(maxTimeChooseI, sheeps);

				if (maxTimeChooseI > maxT) {
					maxT = maxTimeChooseI;
				}

			}

			bw.write(wolfSolve(N) + "");

			br.close();
			bw.close();

		} catch (IOException e) {
			e.printStackTrace();
		}
	}
}