oj.uz

Submission #382260

# Submission time Handle Problem Language Result Execution time Memory
382260 2021-03-26T20:57:50 Z dapig Watching (JOI13_watching) Java 11
50 / 100
 829 ms 114560 KB 

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 = 0;
		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
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 127 ms 12256 KB Output is correct
2 Incorrect 72 ms 8684 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 803 ms 111836 KB Output is correct
2 Correct 73 ms 8444 KB Output is correct
3 Correct 794 ms 110736 KB Output is correct
4 Correct 813 ms 112820 KB Output is correct
5 Correct 804 ms 114560 KB Output is correct
6 Correct 814 ms 110788 KB Output is correct
7 Correct 794 ms 110228 KB Output is correct
8 Correct 790 ms 110784 KB Output is correct
9 Correct 803 ms 111876 KB Output is correct
10 Correct 810 ms 111692 KB Output is correct
11 Correct 829 ms 113132 KB Output is correct
12 Correct 813 ms 112152 KB Output is correct
13 Correct 603 ms 106204 KB Output is correct
14 Correct 666 ms 107436 KB Output is correct
15 Correct 688 ms 107464 KB Output is correct