75 lines
1.3 KiB
Java
75 lines
1.3 KiB
Java
package chelper;
|
|
|
|
import java.util.Arrays;
|
|
|
|
import io.InputReader;
|
|
import io.OutputWriter;
|
|
import misc.GCJSolution;
|
|
import misc.SimpleSavingChelperSolution;
|
|
|
|
|
|
public class TaskB extends GCJSolution {
|
|
|
|
private int m;
|
|
private long total;
|
|
private int n;
|
|
private int[] cap;
|
|
private long[] per;
|
|
private long[] c;
|
|
|
|
public void solve(int testNumber, InputReader in, OutputWriter out) {
|
|
wrapSolve(testNumber, in, out);
|
|
}
|
|
|
|
long get(long time) {
|
|
long[] g = new long[n];
|
|
|
|
for (int i = 0; i < n; i++) {
|
|
g[i] = Math.min(Math.max(0, time - c[i]) / per[i], cap[i]);
|
|
}
|
|
|
|
Arrays.sort(g);
|
|
|
|
long res = 0;
|
|
for (int i = 0; i < m; i++) {
|
|
res += g[n - i - 1];
|
|
}
|
|
|
|
return res;
|
|
}
|
|
|
|
@Override
|
|
public void solve(int testNumber) {
|
|
m = in.nextInt();
|
|
total = in.nextLong();
|
|
n = in.nextInt();
|
|
|
|
cap = new int[n];
|
|
per = new long[n];
|
|
c = new long[n];
|
|
|
|
for (int i = 0; i < n; i++) {
|
|
cap[i] = in.nextInt();
|
|
per[i] = in.nextLong();
|
|
c[i] = in.nextLong();
|
|
}
|
|
|
|
long l = 0;
|
|
long r = Long.MAX_VALUE / 3;
|
|
|
|
while (r - l > 1) {
|
|
long m = (l + r + 1) / 2;
|
|
|
|
long x = get(m);
|
|
|
|
if (x < total) {
|
|
l = m;
|
|
} else {
|
|
r = m;
|
|
}
|
|
}
|
|
|
|
out.println(r);
|
|
}
|
|
}
|