oj.uz

Submission #397165

# Submission time Handle Problem Language Result Execution time Memory
397165 2021-05-01T16:05:57 Z keta_tsimakuridze Watching (JOI13_watching) C++14
100 / 100
 374 ms 31812 KB 
#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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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