Submission #382263

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
382263	2021-03-26T20:58:54 Z	dapig	Watching (JOI13_watching)	Java 11	100 / 100	820 ms	114540 KB

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.0 / 50.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	125 ms	11620 KB	Output is correct
2	Correct	71 ms	8556 KB	Output is correct
3	Correct	74 ms	8536 KB	Output is correct
4	Correct	127 ms	11944 KB	Output is correct
5	Correct	126 ms	11720 KB	Output is correct
6	Correct	127 ms	11900 KB	Output is correct
7	Correct	127 ms	11620 KB	Output is correct
8	Correct	127 ms	11620 KB	Output is correct
9	Correct	128 ms	11720 KB	Output is correct
10	Correct	127 ms	11988 KB	Output is correct
11	Correct	128 ms	12004 KB	Output is correct
12	Correct	125 ms	11748 KB	Output is correct
13	Correct	125 ms	11108 KB	Output is correct
14	Correct	130 ms	11256 KB	Output is correct
15	Correct	126 ms	11396 KB	Output is correct

Subtask #2

50.0 / 50.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	809 ms	111564 KB	Output is correct
2	Correct	71 ms	8520 KB	Output is correct
3	Correct	808 ms	112412 KB	Output is correct
4	Correct	806 ms	111108 KB	Output is correct
5	Correct	805 ms	114540 KB	Output is correct
6	Correct	805 ms	111872 KB	Output is correct
7	Correct	792 ms	110244 KB	Output is correct
8	Correct	799 ms	112068 KB	Output is correct
9	Correct	789 ms	111600 KB	Output is correct
10	Correct	813 ms	111800 KB	Output is correct
11	Correct	820 ms	113192 KB	Output is correct
12	Correct	812 ms	112152 KB	Output is correct
13	Correct	609 ms	105796 KB	Output is correct
14	Correct	675 ms	107384 KB	Output is correct
15	Correct	682 ms	107348 KB	Output is correct