Goldmine
Time limit3sMemory limit512 MB
Given n points and an axis-aligned rectangle of fixed width s and height w, find the maximum number of points the rectangle can cover, borders included.
- Level
Medium7 of 10
- Topics
- Sorting, Two pointers, Sliding window, Prefix sum
- Solved
- No attempts yet
Problem
Byteman, one of the longest-serving and most devoted employees of the Goldmine of Byteland, is about to retire at the end of the year. The mine's management would like to reward him for his conscientious work. As a reward, Byteman may receive a small lot: a rectangular part of the mine whose two sides have lengths and and are parallel to the coordinate axes. He may choose where to place the lot.
The value of a lot depends on where it is placed. The value of a lot is the number of gold nuggets inside it. A nugget lying exactly on the border of the lot still counts as being inside it.
Your task is to write a program that computes the maximum possible value of the lot, that is, its value at the best location. To simplify the problem, assume that the terrain of the mine is unbounded, while the region where nuggets occur is finite.
Write a program that:
- reads the positions of the gold nuggets from standard input,
- computes the maximum value of a lot (the maximum number of nuggets that a lot of the given size can contain),
- writes the result to standard output.
Input
The first line contains two positive integers and separated by a single space (). They are the lengths of the lot's sides parallel to the OX axis and the OY axis, respectively.
The second line contains one positive integer , the number of nuggets in the mine ().
Each of the next lines contains the coordinates of one nugget: two integers and separated by a single space (), giving the -coordinate and the -coordinate of that nugget.
Output
Print a single integer equal to the value of the most valuable lot of the given size.