oj.uz

Submission #948177

# Submission time Handle Problem Language Result Execution time Memory
948177 2024-03-17T19:14:13 Z amirhoseinfar1385 Watching (JOI13_watching) C++17
0 / 100
 28 ms 15452 KB 
#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=-1,high=1e9,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
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2396 KB Output is correct
2 Incorrect 0 ms 468 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 15452 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -