Pagini recente » Cod sursa (job #5892) | Cod sursa (job #2830616) | Cod sursa (job #1911547) | Cod sursa (job #1379070) | Cod sursa (job #1546466)
//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.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 long wolfSolve(int N) {
Heap heap = new Heap(N);
long sum = 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 = Long.parseUnsignedLong((sum + 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();
}
}
}