Submission #417954

#	Time	Username	Problem	Language	Result	Execution time	Memory
417954		bobbilyking	Stove (JOI18_stove)	Java	0 / 100	76 ms	8644 KiB

stove

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++) {
			if (a[i] == e + 1) {
				e = a[i]+1;
			}
			else {
				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: 0 / 20
• Subtask 2: 0 / 30
• Subtask 3: 0 / 50