oj.uz

Submission #417957

# Submission time Handle Problem Language Result Execution time Memory
417957 2021-06-04T16:56:14 Z bobbilyking Stove (JOI18_stove) Java 11
100 / 100
 499 ms 20644 KB 
import java.io.*;
import java.util.*;

public class stove{
	public static void main(String[] args) throws IOException {
		// br = new BufferedReader(new FileReader(".in"));
		// out = new PrintWriter(new FileWriter(".out"));
		//new Thread(null, new (), "peepee", 1<<28).start();
		
		int n =readInt();
		int k = readInt();
		int cost = 0;
		PriorityQueue<Integer> pq = new PriorityQueue<Integer>(Collections.reverseOrder());
		int[] a = new int[n];
		for (int i = 0; i < n; i++) a[i] = readInt();
		List<Integer> st = new ArrayList<Integer>();
		List<Integer> ends = new ArrayList<Integer>();
		int s = a[0];
		int e = a[0]+1;
		st.add(s);
		for (int i =1; i < n; i++) {
			ends.add(e);
			s = a[i];
			e = a[i]+1;
			st.add(s);
		}
		ends.add(e);
		
		cost = ends.get(ends.size()-1) - st.get(0);
		for (int i = 1; i < st.size(); i++) {
			pq.add(st.get(i)-ends.get(i-1));
		}
		while (!pq.isEmpty() && k-->1) {
			cost -= pq.poll();
		}
		out.println(cost);
		out.close();
	}
	
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
	static StringTokenizer st = new StringTokenizer("");
	static String read() throws IOException{return st.hasMoreTokens() ? st.nextToken():(st = new StringTokenizer(br.readLine())).nextToken();}
	static int readInt() throws IOException{return Integer.parseInt(read());}
	static long readLong() throws IOException{return Long.parseLong(read());}
	static double readDouble() throws IOException{return Double.parseDouble(read());}
	
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 8248 KB Output is correct
2 Correct 72 ms 8248 KB Output is correct
3 Correct 72 ms 8340 KB Output is correct
4 Correct 74 ms 8444 KB Output is correct
5 Correct 76 ms 8480 KB Output is correct
6 Correct 75 ms 8488 KB Output is correct
7 Correct 79 ms 8224 KB Output is correct
8 Correct 75 ms 8400 KB Output is correct
9 Correct 74 ms 8352 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 8248 KB Output is correct
2 Correct 72 ms 8248 KB Output is correct
3 Correct 72 ms 8340 KB Output is correct
4 Correct 74 ms 8444 KB Output is correct
5 Correct 76 ms 8480 KB Output is correct
6 Correct 75 ms 8488 KB Output is correct
7 Correct 79 ms 8224 KB Output is correct
8 Correct 75 ms 8400 KB Output is correct
9 Correct 74 ms 8352 KB Output is correct
10 Correct 251 ms 12056 KB Output is correct
11 Correct 211 ms 11912 KB Output is correct
12 Correct 226 ms 11988 KB Output is correct
13 Correct 237 ms 12340 KB Output is correct
14 Correct 288 ms 12416 KB Output is correct
15 Correct 223 ms 12072 KB Output is correct

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 8248 KB Output is correct
2 Correct 72 ms 8248 KB Output is correct
3 Correct 72 ms 8340 KB Output is correct
4 Correct 74 ms 8444 KB Output is correct
5 Correct 76 ms 8480 KB Output is correct
6 Correct 75 ms 8488 KB Output is correct
7 Correct 79 ms 8224 KB Output is correct
8 Correct 75 ms 8400 KB Output is correct
9 Correct 74 ms 8352 KB Output is correct
10 Correct 251 ms 12056 KB Output is correct
11 Correct 211 ms 11912 KB Output is correct
12 Correct 226 ms 11988 KB Output is correct
13 Correct 237 ms 12340 KB Output is correct
14 Correct 288 ms 12416 KB Output is correct
15 Correct 223 ms 12072 KB Output is correct
16 Correct 387 ms 20328 KB Output is correct
17 Correct 390 ms 20456 KB Output is correct
18 Correct 419 ms 20364 KB Output is correct
19 Correct 422 ms 20444 KB Output is correct
20 Correct 499 ms 20580 KB Output is correct
21 Correct 474 ms 20508 KB Output is correct
22 Correct 452 ms 20440 KB Output is correct
23 Correct 477 ms 20644 KB Output is correct
24 Correct 455 ms 20284 KB Output is correct