Submission #948181

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
948181	2024-03-17T19:20:48 Z	amirhoseinfar1385	Watching (JOI13_watching)	C++17	100 / 100	188 ms	16168 KB

watching

#include<bits/stdc++.h>
using namespace std;
const int maxn=2005;
int n,a,b,all[maxn],dp[maxn][maxn];

void vorod(){
	cin>>n>>a>>b;
	a=min(n,a);
	b=min(n,b);
	for(int i=1;i<=n;i++){
		cin>>all[i];
	}
	sort(all+1,all+n+1);
}

int check(int len){
	for(int i=1;i<=n;i++){
		int l1=0,l2=0;
		while(l1+1<i&&all[i]-all[l1+1]+1>len*2){
			l1++;
		}
		while(l2+1<i&&all[i]-all[l2+1]+1>len){
			l2++;
		}
		for(int j=0;j<=a;j++){
			dp[i][j]=dp[l1][j]+1;
			if(j>0){
				dp[i][j]=min(dp[i][j],dp[l2][j-1]);
			}
			//cout<<i<<" "<<j<<" "<<dp[i][j]<<endl;
		}
	}
	return dp[n][a]<=b;
}

void solve(){
	int low=0,high=2e9+1,mid;
	while(high-low>1){
		mid=(high+low)>>1;
		if(check(mid)){
			high=mid;
		}else{
			low=mid;
		}
	}
	cout<<high<<"\n";
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
//	freopen("inp.txt","r",stdin);
	vorod();
	solve();
}

Subtask #1

50.0 / 50.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	2648 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	1 ms	2396 KB	Output is correct
5	Correct	1 ms	2396 KB	Output is correct
6	Correct	1 ms	2396 KB	Output is correct
7	Correct	1 ms	2396 KB	Output is correct
8	Correct	1 ms	2396 KB	Output is correct
9	Correct	1 ms	2396 KB	Output is correct
10	Correct	1 ms	2396 KB	Output is correct
11	Correct	1 ms	2392 KB	Output is correct
12	Correct	1 ms	2396 KB	Output is correct
13	Correct	1 ms	2512 KB	Output is correct
14	Correct	1 ms	2652 KB	Output is correct
15	Correct	1 ms	2396 KB	Output is correct

Subtask #2

50.0 / 50.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	30 ms	15452 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	161 ms	16156 KB	Output is correct
4	Correct	179 ms	16164 KB	Output is correct
5	Correct	73 ms	15556 KB	Output is correct
6	Correct	181 ms	16160 KB	Output is correct
7	Correct	61 ms	15512 KB	Output is correct
8	Correct	91 ms	15452 KB	Output is correct
9	Correct	122 ms	16028 KB	Output is correct
10	Correct	188 ms	16168 KB	Output is correct
11	Correct	77 ms	15448 KB	Output is correct
12	Correct	127 ms	15964 KB	Output is correct
13	Correct	62 ms	15696 KB	Output is correct
14	Correct	67 ms	15516 KB	Output is correct
15	Correct	68 ms	15448 KB	Output is correct