import java.io.*;
import java.math.*;
import java.util.*;
import java.util.function.*;
public class watching {
static boolean debug = false;
public static void main(String[] args) {
Scanner sc = new Scanner();
int n = sc.nextInt();
int p = sc.nextInt();
int q = sc.nextInt();
long[] arr = sc.nextLongArray(n);
Arrays.sort(arr);
if(p + q >= n) {
println(1);
return;
}
TreeMap<Long, Integer> map = new TreeMap<>();
for(int i = 0; i < n; i++) {
map.put(arr[i], i);
}
println(lowerBound(1L, 1_000_000_000_000L, true, w -> {
int[][] dp = new int[p + 1][q + 1];
dp[0][0] = 0;
for(int i = 0; i <= p; i++) {
for(int j = 0; j <= q; j++) {
int val = dp[i][j];
if(val == n) {
if(i < p) dp[i + 1][j] = n;
if(j < q) dp[i][j + 1] = n;
continue;
}
if(i < p) {
Map.Entry<Long, Integer> temp = map.ceilingEntry(arr[dp[i][j]] + w);
dp[i + 1][j] = Math.max(dp[i + 1][j], temp == null ? n : temp.getValue());
}
if(j < q) {
Map.Entry<Long, Integer> temp = map.ceilingEntry(arr[dp[i][j]] + 2 * w);
dp[i][j + 1] = Math.max(dp[i][j + 1], temp == null ? n : temp.getValue());
}
}
}
return dp[p][q] == n;
}, 0));
flush();
}
@SuppressWarnings("all")
static <U extends Comparable<U>> int lowerBound(int l, int r, U target, Function<Integer, U> function) {
while(l < r) {
int mid = (l + r) >> 1;
U curr = function.apply(mid);
int c = curr.compareTo(target);
if(c < 0) {
l = mid + 1;
}
else {
r = mid;
}
}
return l;
}
@SuppressWarnings("all")
static <U extends Comparable<U>> long lowerBound(long l, long r, U target, Function<Long, U> function, long ignored) {
while(l < r) {
long mid = (l + r) >> 1;
U curr = function.apply(mid);
int c = curr.compareTo(target);
if(c < 0) {
l = mid + 1;
}
else {
r = mid;
}
}
return l;
}
@SuppressWarnings("all")
static PrintWriter pw = new PrintWriter(System.out);
@SuppressWarnings("all")
static String delim = " ";
@SuppressWarnings("all")
static void println() {
pw.println();
if(debug) pw.flush();
}
@SuppressWarnings("all")
static void print(Object x) {
if(x != null && x.getClass().isArray()) {
String result;
if(x instanceof int[]) {
result = Arrays.toString((int[]) x);
}
else if(x instanceof long[]) {
result = Arrays.toString((long[]) x);
}
else if(x instanceof double[]) {
result = Arrays.toString((double[]) x);
}
else if(x instanceof float[]) {
result = Arrays.toString((float[]) x);
}
else if(x instanceof boolean[]) {
result = Arrays.toString((boolean[]) x);
}
else if(x instanceof short[]) {
result = Arrays.toString((short[]) x);
}
else if(x instanceof char[]) {
result = Arrays.toString((char[]) x);
}
else if(x instanceof byte[]) {
result = Arrays.toString((byte[]) x);
}
else {
result = Arrays.toString((Object[]) x);
}
pw.print(result);
}
else {
pw.print(x);
}
if(debug) pw.flush();
}
@SuppressWarnings("all")
static <T> void println(Object x) {
print(x);
println();
}
@SuppressWarnings("all")
static <T> void iterPrint(Iterable<T> arr) {
boolean space = false;
for(T t : arr) {
if(space) print(delim);
print(t);
space = true;
}
println();
}
@SuppressWarnings("all")
static <T> void iterPrint(T[] arr) {
boolean space = false;
for (T t : arr) {
if (space) print(delim);
print(t);
space = true;
}
println();
}
@SuppressWarnings("all")
static void iterPrint(int[] arr) {
boolean space = false;
for (int t : arr) {
if (space) print(delim);
print(t);
space = true;
}
println();
}
@SuppressWarnings("all")
static void iterPrint(long[] arr) {
boolean space = false;
for (long t : arr) {
if (space) print(delim);
print(t);
space = true;
}
println();
}
@SuppressWarnings("all")
static void iterPrint(double[] arr) {
boolean space = false;
for (double t : arr) {
if (space) print(delim);
print(t);
space = true;
}
println();
}
@SuppressWarnings("all")
static void iterPrint(char[] arr) {
boolean space = false;
for (char t : arr) {
if (space) print(delim);
print(t);
space = true;
}
println();
}
@SuppressWarnings("all")
static void iterPrint(boolean[] arr) {
boolean space = false;
for (boolean t : arr) {
if (space) print(delim);
print(t);
space = true;
}
println();
}
@SuppressWarnings("all")
static void printf(String format, Object... args) {
pw.printf(format, args);
if(debug) pw.flush();
}
static void flush() {
pw.flush();
}
@SuppressWarnings("all")
static class Scanner {
BufferedReader br;
StringTokenizer curr;
String delim = " \t\n\r\f";
Scanner() {
br = new BufferedReader(new InputStreamReader(System.in));
}
Scanner(String fileName) {
try {
br = new BufferedReader(new FileReader(fileName));
} catch (FileNotFoundException e) {
e.printStackTrace();
System.out.println("Switching to stdin...");
br = new BufferedReader(new InputStreamReader(System.in));
}
}
boolean setDelimiter(String delim) {
this.delim = delim;
return curr == null;
}
String getDelimiter() {
return delim;
}
String next() {
if(curr == null) {
try {
curr = new StringTokenizer(br.readLine(), delim);
} catch (IOException e) {
return null;
}
}
String result = curr.nextToken();
if(!curr.hasMoreTokens()) curr = null;
return result;
}
int nextInt() {
return Integer.parseInt(next());
}
long nextLong() {
return Long.parseLong(next());
}
double nextDouble() {
return Double.parseDouble(next());
}
BigInteger nextBigInteger() {
return new BigInteger(next());
}
boolean nextBoolean() {
return Boolean.parseBoolean(next());
}
boolean[] nextBinaryString() {
return nextBinaryString('1');
}
boolean[] nextBinaryString(char truth) {
String s = next();
int n = s.length();
boolean[] result = new boolean[n];
for(int i = 0; i < n; i++) {
result[i] = s.charAt(i) == truth;
}
return result;
}
String nextLine() {
if(curr == null) {
try {
return br.readLine();
}
catch(IOException e) {
return null;
}
}
StringBuilder remaining = new StringBuilder();
remaining.append(curr.nextToken());
while(curr.hasMoreTokens()) {
remaining.append(' ').append(curr.nextToken());
}
return remaining.toString();
}
String[] nextStringArray(int n) {
String[] arr = new String[n];
for(int i = 0; i < n; i++) {
arr[i] = next();
}
return arr;
}
int[] nextIntArray(int n) {
int[] arr = new int[n];
for(int i = 0; i < n; i++) {
arr[i] = nextInt();
}
return arr;
}
long[] nextLongArray(int n) {
long[] arr = new long[n];
for(int i = 0; i < n; i++) {
arr[i] = nextLong();
}
return arr;
}
double[] nextDoubleArray(int n) {
double[] arr = new double[n];
for(int i = 0; i < n; i++) {
arr[i] = nextDouble();
}
return arr;
}
BigInteger[] nextBigIntegerArray(int n) {
BigInteger[] arr = new BigInteger[n];
for(int i = 0; i < n; i++) {
arr[i] = nextBigInteger();
}
return arr;
}
boolean[] nextBooleanArray(int n) {
boolean[] arr = new boolean[n];
for(int i = 0; i < n; i++) {
arr[i] = nextBoolean();
}
return arr;
}
List<String> nextStringList(int n) {
List<String> list = new ArrayList<>(n);
for(int i = 0; i < n; i++) {
list.add(next());
}
return list;
}
List<Integer> nextIntList(int n) {
List<Integer> list = new ArrayList<>(n);
for(int i = 0; i < n; i++) {
list.add(nextInt());
}
return list;
}
List<Long> nextLongList(int n) {
List<Long> list = new ArrayList<>(n);
for(int i = 0; i < n; i++) {
list.add(nextLong());
}
return list;
}
List<Double> nextDoubleList(int n) {
List<Double> list = new ArrayList<>(n);
for(int i = 0; i < n; i++) {
list.add(nextDouble());
}
return list;
}
List<BigInteger> nextBigIntegerList(int n) {
List<BigInteger> list = new ArrayList<>(n);
for(int i = 0; i < n; i++) {
list.add(nextBigInteger());
}
return list;
}
List<Boolean> nextBooleanList(int n) {
List<Boolean> list = new ArrayList<>(n);
for(int i = 0; i < n; i++) {
list.add(nextBoolean());
}
return list;
}
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
60 ms |
9876 KB |
Output is correct |
| 2 |
Incorrect |
47 ms |
9244 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
213 ms |
17256 KB |
Output is correct |
| 2 |
Incorrect |
47 ms |
8852 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
