結果

問題 No.3513 Greedy Yokan Party
コンテスト
ユーザー msksknkn
提出日時 2026-05-02 20:45:13
言語 Java
(openjdk 25.0.2)
コンパイル:
javac -encoding UTF8 _filename_
実行:
java -ea -Xmx700m -Xss256M -DONLINE_JUDGE=true _class_
結果
AC  
実行時間 1,339 ms / 2,000 ms
コード長 1,769 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 3,662 ms
コンパイル使用メモリ 81,672 KB
実行使用メモリ 82,984 KB
最終ジャッジ日時 2026-05-02 20:45:48
合計ジャッジ時間 30,371 ms
ジャッジサーバーID
（参考情報） 		judge3_0 / judge1_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 26
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

package no3513;
import java.util.*;
public class Main {

	public static void main(String[] args) {
		// TODO 自動生成されたメソッド・スタブ
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int l = sc.nextInt();
		int k = sc.nextInt();
		int[] a = new int[n + 2];
		for(int i = 1;i <= n;i++) {
			a[i] = sc.nextInt();
		}a[n + 1] = l;
		//この大きさ以上のようかんが2個用意できるorできない
		int left = 0;
		int right = l;
		int INF = n + 1;
		while(left < right - 1) {
			int mid = (left + right)/2;
			//dp[i][j] = mid以上のようかんをすでに切り出した個数がi個で、
			//j個目の切れ込みまで見終わったときの切れ込みをスルーした数の最小値
			int[][] dp = new int[3][n + 2];
			for(int i = 0;i <= n + 1;i++) {
				dp[0][i] = INF;
				dp[1][i] = INF;
				dp[2][i] = INF;
			}dp[0][0] = 0;
			for(int i = 0;i <= n;i++) {
				int ind = binSearch(mid + a[i],a,n);
				//mid以上のようかんを切り出す
				if(ind != n + 2) {
					for(int j = 0;j < 2;j++) {
						dp[j + 1][ind] = Math.min(dp[j + 1][ind],dp[j][i] + ind - i - 1);
					}
				}
				//ようかんを切り出さない(切れ込みをスルーしない
				for(int j = 0;j <= 2;j++) {
					dp[j][i + 1] = Math.min(dp[j][i + 1],dp[j][i]);
				}
			}//System.out.println(dp[2][n + 1] + " " + mid);
			//切れ込みをスルーできる数はn - k
			if(dp[2][n + 1] <= n - k) {
				left = mid;
			}else {
				right = mid;
			}
		}System.out.println(left);
	}static int binSearch(int target,int[] a,int n) {
		int left = 0;
		int right = n + 2;
		while(left < right - 1) {
			int mid = (left + right)/2;
			if(a[mid] < target) {
				left = mid;
			}else {
				right = mid;
			}
		}return right;
	}

}
0