답안 #397978

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
397978	2021-05-03T13:14:44 Z	lukameladze	구경하기 (JOI13_watching)	C++14	100 / 100	406 ms	31856 KB

watching

# include <bits/stdc++.h>
#define f first
#define s second
#define pb push_back
using namespace std;
const int N=2005;
long long le,ri,mid,n,a[N],m,pr[N],pr1[N],dp[N][N],w,k,ans;
int check(int mid) {
	for (int i=0; i<=n; i++) {
		for (int j=0; j<=n; j++) {
			dp[i][j]=1e9;
		}
	}
	dp[0][0]=0;
	w=mid;
	for (int i=1; i<=n; i++) {
		pr[i]=pr1[i]=0;
		for (int j=i; j>=1; j--) {
			if (a[i]-a[j]>=w && !pr[i]) {
				pr[i]=j;
			//	break;
			}
			if (a[i]-a[j]>=2*w && !pr1[i]) {
				pr1[i]=j;
			//	break;
			}
		}
	//	cout<<i<<" "<<pr[i]<<" "<<pr1[i]<<endl;
	}
	for (int i=1; i<=n; i++) {
		for (int j=0; j<=min(m,(long long)i); j++) {
			if(j)
			dp[i][j]=dp[pr[i]][j-1];
			dp[i][j]=min(dp[i][j],dp[pr1[i]][j]+1);
			if (i==n && dp[n][j]<=k) return 1;
		}
	}
	//if (dp[n][m]<=k) return 1;
	return 0;
}
int main() {
	cin>>n>>m>>k;
	for (int i=1; i<=n; i++) {
		cin>>a[i];
	}
	sort(a+1, a+n+1);
	for (int i=1; i<=n; i++) {
		for (int j=i; j>=1; j--) {
			if (a[i]-a[j]>w) {
				pr[i]=j;
				break;
			}
			if (a[i]-a[j]>2*w) {
				pr1[i]=j;
				break;
			}
		}
	}
	le=1;
	ri=1e9;
	while (le<=ri) {
		mid=(le+ri)/2;
		if (check(mid)) {
			ri=mid-1;
			ans=mid;
		}
		else {
			le=mid+1;
		}
	}
	cout<<ans<<endl;
}

Subtask #1

50.0 / 50.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	716 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Correct	1 ms	332 KB	Output is correct
4	Correct	2 ms	692 KB	Output is correct
5	Correct	2 ms	716 KB	Output is correct
6	Correct	2 ms	716 KB	Output is correct
7	Correct	2 ms	716 KB	Output is correct
8	Correct	2 ms	716 KB	Output is correct
9	Correct	2 ms	716 KB	Output is correct
10	Correct	2 ms	716 KB	Output is correct
11	Correct	2 ms	716 KB	Output is correct
12	Correct	2 ms	716 KB	Output is correct
13	Correct	1 ms	716 KB	Output is correct
14	Correct	2 ms	716 KB	Output is correct
15	Correct	1 ms	716 KB	Output is correct

Subtask #2

50.0 / 50.0

#	결과	실행 시간	메모리	Grader output
1	Correct	231 ms	31692 KB	Output is correct
2	Correct	1 ms	332 KB	Output is correct
3	Correct	368 ms	31752 KB	Output is correct
4	Correct	382 ms	31692 KB	Output is correct
5	Correct	257 ms	31820 KB	Output is correct
6	Correct	381 ms	31748 KB	Output is correct
7	Correct	262 ms	31856 KB	Output is correct
8	Correct	280 ms	31692 KB	Output is correct
9	Correct	334 ms	31812 KB	Output is correct
10	Correct	406 ms	31748 KB	Output is correct
11	Correct	282 ms	31736 KB	Output is correct
12	Correct	355 ms	31796 KB	Output is correct
13	Correct	254 ms	31812 KB	Output is correct
14	Correct	258 ms	31696 KB	Output is correct
15	Correct	256 ms	31692 KB	Output is correct