Submission #417957

#TimeUsernameProblemLanguageResultExecution timeMemory
417957bobbilykingStove (JOI18_stove)Java
100 / 100
499 ms20644 KiB
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());}
	
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...