Submission #2545433
Source Code Expand
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
private static Scanner sc;
private static int[][] neg8 = new int[][]{{-1, -1}, {0, -1}, {1, -1}, {-1, 0}, {1, 0}, {-1, 1}, {0, 1}, {1, 1}};
private static int[][] neg4 = new int[][]{{1, 0}, {0, -1}, {-1, 0}, {0, 1}};
public static void main(String[] args) {
Main instance = new Main();
sc = instance.new Scanner();
instance.solve();
}
private static class Machine {
final long a;
final long b;
private Machine(long a, long b) {
this.a = a;
this.b = b;
}
long time(int count) {
return a + (count - 1) * b;
}
}
private void solve() {
try {
int N=sc.nextInt();
long K=sc.nextLong();
Machine[] arr = new Machine[N];
for (int i = 0; i < N; i++) {
arr[i] = new Machine(sc.nextLong(), sc.nextLong());
}
Arrays.sort(arr, new Comparator<Machine>() {
@Override
public int compare(Machine o1, Machine o2) {
return (int) (o1.a - o2.a);
}
});
PriorityQueue<Long> q = new PriorityQueue<>();
for (int i = 0; i < N; i++) {
for (int j = 1; j <= 100000; j++) {
q.add(arr[i].time(j));
}
}
long ans = 0;
for (int i = 0; i <K ; i++) {
ans+=q.poll();
}
System.out.println(ans);
} catch (Exception e) {
e.printStackTrace();
}
}
private class Scanner {
String[] s;
int i;
BufferedReader br;
String regex = " ";
public Scanner() {
s = new String[0];
i = 0;
br = new BufferedReader(new InputStreamReader(System.in));
}
@Override
protected void finalize() throws Throwable {
try {
super.finalize();
} finally {
destruction();
}
}
private void destruction() throws IOException {
if (br != null) br.close();
}
public String next() throws IOException {
if (i < s.length) return s[i++];
String st = br.readLine();
while (st == "") st = br.readLine();
s = st.split(regex, 0);
i = 0;
return s[i++];
}
public int nextInt() throws NumberFormatException, IOException {
return Integer.parseInt(next());
}
public Long nextLong() throws NumberFormatException, IOException {
return Long.parseLong(next());
}
public Double nextDouble() throws NumberFormatException, IOException {
return Double.parseDouble(next());
}
}
private static double distance(int x1, int x2, int y1, int y2) {
return Math.sqrt((Math.pow(x1 - x2, 2) + Math.pow(y1 - y2, 2)));
}
private static boolean nextPermutation(int[] nums) {
int i = nums.length - 2;
while (i >= 0 && nums[i + 1] <= nums[i]) {
i--;
}
boolean swap = false;
if (i >= 0) {
int j = nums.length - 1;
while (j >= 0 && nums[j] <= nums[i]) {
j--;
}
swap(nums, i, j);
swap = true;
}
reverse(nums, i + 1);
return swap;
}
private static void reverse(int[] nums, int start) {
int i = start, j = nums.length - 1;
while (i < j) {
swap(nums, i, j);
i++;
j--;
}
}
private static void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
private static ArrayList filledList(int n, int fill) {
return new ArrayList<>(Collections.nCopies(n, fill));
}
// 指定した値`以上`の要素が最初に現れる位置を返す
private static int lower_bound(List<Integer> list, int val) {
return ~Collections.binarySearch(list, val, (x, y) -> x.compareTo(y) >= 0 ? 1 : -1);
}
// 指定した値`より大きい`の要素が最初に現れる位置を返す
private static int upper_bound(List<Integer> list, int val) {
return ~Collections.binarySearch(list, val, (x, y) -> x.compareTo(y) > 0 ? 1 : -1);
}
}
Submission Info
Submission Time |
|
Task |
C - Factory |
User |
jun0sck |
Language |
Java8 (OpenJDK 1.8.0) |
Score |
0 |
Code Size |
4769 Byte |
Status |
TLE |
Exec Time |
2113 ms |
Memory |
574520 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
0 / 300 |
Status |
|
|
Set Name |
Test Cases |
Sample |
sample_01.txt, sample_02.txt, sample_03.txt |
All |
sample_01.txt, sample_02.txt, sample_03.txt, subtask_1_1.txt, subtask_1_10.txt, subtask_1_11.txt, subtask_1_12.txt, subtask_1_13.txt, subtask_1_14.txt, subtask_1_15.txt, subtask_1_16.txt, subtask_1_17.txt, subtask_1_18.txt, subtask_1_2.txt, subtask_1_3.txt, subtask_1_4.txt, subtask_1_5.txt, subtask_1_6.txt, subtask_1_7.txt, subtask_1_8.txt, subtask_1_9.txt |
Case Name |
Status |
Exec Time |
Memory |
sample_01.txt |
AC |
117 ms |
29140 KB |
sample_02.txt |
AC |
199 ms |
62292 KB |
sample_03.txt |
AC |
150 ms |
26324 KB |
subtask_1_1.txt |
AC |
120 ms |
32852 KB |
subtask_1_10.txt |
TLE |
2106 ms |
327540 KB |
subtask_1_11.txt |
AC |
97 ms |
24020 KB |
subtask_1_12.txt |
TLE |
2113 ms |
574520 KB |
subtask_1_13.txt |
AC |
90 ms |
23252 KB |
subtask_1_14.txt |
TLE |
2112 ms |
453704 KB |
subtask_1_15.txt |
TLE |
2111 ms |
400912 KB |
subtask_1_16.txt |
AC |
155 ms |
28628 KB |
subtask_1_17.txt |
AC |
148 ms |
23252 KB |
subtask_1_18.txt |
TLE |
2113 ms |
567772 KB |
subtask_1_2.txt |
TLE |
2112 ms |
436636 KB |
subtask_1_3.txt |
TLE |
2113 ms |
428420 KB |
subtask_1_4.txt |
TLE |
2111 ms |
425532 KB |
subtask_1_5.txt |
TLE |
2113 ms |
568268 KB |
subtask_1_6.txt |
TLE |
2111 ms |
418108 KB |
subtask_1_7.txt |
MLE |
1899 ms |
409900 KB |
subtask_1_8.txt |
TLE |
2110 ms |
492600 KB |
subtask_1_9.txt |
TLE |
2111 ms |
496368 KB |