Submission #1951533
Source Code Expand
import java.io.BufferedReader; import java.io.Closeable; import java.io.IOException; import java.io.InputStream; import java.io.InputStreamReader; import java.io.PrintWriter; import java.util.ArrayList; import java.util.Arrays; import java.util.Collections; import java.util.Comparator; import java.util.HashMap; import java.util.HashSet; import java.util.LinkedList; import java.util.ListIterator; import java.util.Map.Entry; import java.util.PriorityQueue; import java.util.Scanner; import java.util.StringTokenizer; import java.util.TreeMap; import java.util.TreeSet; public class Main { public static void main(String[] args) throws IOException { try (Scanner sc = new Scanner(System.in)) { final int N = sc.nextInt(); final long H = sc.nextLong(); PriorityQueue<Long> a_queue = new PriorityQueue<Long>(N, Collections.reverseOrder()); PriorityQueue<Long> b_queue = new PriorityQueue<Long>(N, Collections.reverseOrder()); for(int i = 0; i < N; i++){ final long a = sc.nextLong(); final long b = sc.nextLong(); a_queue.add(a); b_queue.add(b); } int b_count = 0; long b_sum = 0; long min = Long.MAX_VALUE; while(!a_queue.isEmpty()){ final long a = a_queue.poll(); while(b_sum < H && !b_queue.isEmpty()){ if(b_queue.peek() < a){ break; } b_count++; b_sum += b_queue.poll(); } //System.out.println(a + " " + b_sum); final long a_count = (Math.max(0, H - b_sum) + (a - 1)) / a; min = Math.min(min, b_count + a_count); } System.out.println(min); } } public static class Scanner implements Closeable { private BufferedReader br; private StringTokenizer tok; public Scanner(InputStream is) throws IOException { br = new BufferedReader(new InputStreamReader(is)); } private void getLine() throws IOException { while (!hasNext()) { tok = new StringTokenizer(br.readLine()); } } private boolean hasNext() { return tok != null && tok.hasMoreTokens(); } public String next() throws IOException { getLine(); return tok.nextToken(); } public int nextInt() throws IOException { return Integer.parseInt(next()); } public long nextLong() throws IOException { return Long.parseLong(next()); } public double nextDouble() throws IOException { return Double.parseDouble(next()); } public int[] nextIntArray(int n) throws IOException { final int[] ret = new int[n]; for (int i = 0; i < n; i++) { ret[i] = this.nextInt(); } return ret; } public long[] nextLongArray(int n) throws IOException { final long[] ret = new long[n]; for (int i = 0; i < n; i++) { ret[i] = this.nextLong(); } return ret; } public void close() throws IOException { br.close(); } } }
Submission Info
Submission Time | |
---|---|
Task | D - Katana Thrower |
User | mondatto |
Language | Java8 (OpenJDK 1.8.0) |
Score | 400 |
Code Size | 2917 Byte |
Status | AC |
Exec Time | 383 ms |
Memory | 50508 KB |
Judge Result
Set Name | Sample | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 400 / 400 | ||||
Status |
|
|
Set Name | Test Cases |
---|---|
Sample | a01, a02, a03, a04 |
All | a01, a02, a03, a04, b05, b06, b07, b08, b09, b10, b11, b12, b13, b14, b15, b16, b17, b18, b19, b20, b21, b22, b23, b24 |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
a01 | AC | 77 ms | 20436 KB |
a02 | AC | 76 ms | 20052 KB |
a03 | AC | 75 ms | 20180 KB |
a04 | AC | 78 ms | 20692 KB |
b05 | AC | 76 ms | 18900 KB |
b06 | AC | 291 ms | 47312 KB |
b07 | AC | 76 ms | 20948 KB |
b08 | AC | 300 ms | 50508 KB |
b09 | AC | 77 ms | 22484 KB |
b10 | AC | 76 ms | 19028 KB |
b11 | AC | 74 ms | 21204 KB |
b12 | AC | 75 ms | 21204 KB |
b13 | AC | 245 ms | 39700 KB |
b14 | AC | 239 ms | 39064 KB |
b15 | AC | 222 ms | 40120 KB |
b16 | AC | 246 ms | 42416 KB |
b17 | AC | 329 ms | 41992 KB |
b18 | AC | 377 ms | 42844 KB |
b19 | AC | 304 ms | 42612 KB |
b20 | AC | 325 ms | 42824 KB |
b21 | AC | 330 ms | 38304 KB |
b22 | AC | 383 ms | 41896 KB |
b23 | AC | 79 ms | 20308 KB |
b24 | AC | 124 ms | 20564 KB |