제출 #1279826

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1279826		cmiuc	구경하기 (JOI13_watching)	C++20	100 / 100	195 ms	16144 KiB

watching

#include <iostream>
#include <algorithm>

using namespace std;
const int N = 2005;
int dp[N][N], a[N], NxtP[N], NxtQ[N];

int MinQ(int n, int p, int w){
	for (int i=1, r = 1, R = 1;i<=n;i++){
		while (r < n and a[r+1] - a[i] + 1 <= w)
			r++;
		while (R < n and a[R+1] - a[i] + 1 <= 2 * w)
			R++;
		NxtP[i] = r;
		NxtQ[i] = R;
	}

	for (int i=0;i<=n;i++){
		for (int j=0;j<=p;j++)
			dp[i][j] = 1e9;
	}
	dp[0][0] = 0;
	int Ans = 1e9;

	for (int i=1;i<=n;i++){
		for (int j=0;j<=p;j++){
			dp[NxtQ[i]][j] = min(dp[NxtQ[i]][j], dp[i-1][j] + 1);
			dp[NxtP[i]][j+1] = min(dp[NxtP[i]][j+1], dp[i-1][j]);

			if (i == n and Ans > dp[i][j])
				Ans = dp[i][j];
		}
	}
	return Ans;
}

int main(){
	int n, p, q;
	cin>>n>>p>>q;
	p = min(p, n);
	q = min(q, n);

	for (int i=1;i<=n;i++)
		cin>>a[i];
	sort(a + 1, a + n + 1);

	int l = 0, r = 1e9;

	while (l + 1 < r){
		int mid = (l + r) / 2;
		if (MinQ(n, p, mid) <= q)
			r = mid;
		else
			l = mid;
	}
	cout<<r<<'\n';
}

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