답안 #397165

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
397165	2021-05-01T16:05:57 Z	keta_tsimakuridze	구경하기 (JOI13_watching)	C++14	100 / 100	374 ms	31812 KB

watching

#include<bits/stdc++.h>
#define f first
#define int long long
#define s second
using namespace std;
const int N=2e3+5,mod=1e9+7,Inf=1e7;
int t,dp[N][N],a[N],n,p,q;
string s;
bool check(int w){
	//cout<<"++";
	for(int i=1;i<=n;i++){
		int l1 = 0, l2 = 0;
		for(int j=n;j>=0;j--) dp[i][j]=Inf;
		for(int j=i;j>=0;j--) {
			while(a[l1+1]<=a[i]-w) l1++;
			while(a[l2+1]<=a[i]-w*2) l2++;
			if(j)dp[i][j] = min(dp[l1][j-1],dp[i][j]);
			dp[i][j] = min(dp[i][j],dp[l2][j] + 1);
		}
	}
	for(int i=0;i<=min(p,n);i++){
    //	cout<<dp[n][i]<<" ";
		if(dp[n][i] <= q) return 1;
	}
	return 0;
}
 main(){
	// t=1;
	cin>>n>>p>>q;
	for(int i=1;i<=n;i++){
		cin >> a[i];
	}
	sort(a+1,a+n+1);
	int l=1,r=1e9+1,ans=0;
	while(l<=r){
		int mid=(l+r)/2;
		if(check(mid)){
			r=mid-1;
			ans=mid;
		}
		else l=mid+1;
	}
	cout<<ans;
}

Compilation message

watching.cpp:27:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   27 |  main(){
      |       ^

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	336 KB	Output is correct
4	Correct	2 ms	716 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	3 ms	716 KB	Output is correct
9	Correct	2 ms	716 KB	Output is correct
10	Correct	2 ms	688 KB	Output is correct
11	Correct	2 ms	716 KB	Output is correct
12	Correct	2 ms	716 KB	Output is correct
13	Correct	2 ms	716 KB	Output is correct
14	Correct	2 ms	716 KB	Output is correct
15	Correct	2 ms	716 KB	Output is correct

Subtask #2

50.0 / 50.0

#	결과	실행 시간	메모리	Grader output
1	Correct	340 ms	31708 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Correct	359 ms	31684 KB	Output is correct
4	Correct	358 ms	31684 KB	Output is correct
5	Correct	360 ms	31812 KB	Output is correct
6	Correct	367 ms	31728 KB	Output is correct
7	Correct	367 ms	31812 KB	Output is correct
8	Correct	372 ms	31708 KB	Output is correct
9	Correct	374 ms	31788 KB	Output is correct
10	Correct	373 ms	31724 KB	Output is correct
11	Correct	374 ms	31708 KB	Output is correct
12	Correct	371 ms	31712 KB	Output is correct
13	Correct	368 ms	31708 KB	Output is correct
14	Correct	370 ms	31712 KB	Output is correct
15	Correct	373 ms	31704 KB	Output is correct