oj.uz

답안 #382263

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
382263 2021-03-26T20:58:54 Z dapig 구경하기 (JOI13_watching) Java 11
100 / 100
 820 ms 114540 KB 
//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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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