Submission #382263

#	Time	Username	Problem	Language	Result	Execution time	Memory
382263		dapig	Watching (JOI13_watching)	Java	100 / 100	820 ms	114540 KiB

watching

//package week3;

import java.io.*;
import java.util.*;

class watching {

	public static void main(String[] args) throws IOException {

		watching obj = new watching();

		obj.doStuff();

	}
	
	int bs(int v) {
		int l = 0, r = pos.length;
		int best = 0;
		while (l < r) {
			int m = (l+r)/2;
			if (v > pos[m]) {
				best = m;
				l = m+1;
			} else r = m;
		}
		return best;
	}
	
	int process(int v) {
		dp = new int[pos.length][pos.length+1]; // [pos in array][given x long cams, how many smalls]
		for (int i = 1; i < dp.length; i++) {
			// just one
			int res = bs(pos[i]-v+1);
			for (int j = 0; j < dp[0].length; j++) {
				dp[i][j] = dp[res][j]+1;
			}
			// double
			res = bs(pos[i]-(2*v)+1);
			for (int j = 0; j < dp[0].length-1; j++) {
				dp[i][j+1] = Math.min(dp[i][j+1], dp[res][j]);
			}
		}
		return (dp[dp.length-1][Math.min(dp[0].length-1, q)]);
	}

	int n, p, q;
	int[] pos;
	int[][] dp;
	private void doStuff() throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken());
		p = Integer.parseInt(st.nextToken());
		q = Integer.parseInt(st.nextToken());
		pos = new int[n+1];
		for (int i = 1; i < pos.length; i++) {
			pos[i] = Integer.parseInt(br.readLine());
		}
		br.close();

		Arrays.sort(pos);
		int l = 1, r = pos[pos.length-1]-pos[1]+1;
		int best = 1;
		while (l < r) {
			int m = (l+r)/2;
			int val = process(m);
			if (val <= p) {
				best = m;
				r = m;
			} else l = m+1;
		}
		
		System.out.println(best);
		
	}

}

• Subtask 1: 50 / 50
• Subtask 2: 50 / 50