Submission #947120

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
947120	2024-03-15T14:09:06 Z	sandrofeiqrishvili	Watching (JOI13_watching)	C++14	100 / 100	171 ms	32212 KB

watching

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define ff first
#define ss second
#define int long long
const int N = 2005, inf=1e18;
int n, p, q, a[N], dp[N][N],l1,l2;
set <pair <int, int> > s;
int ans;
bool check(int mid){
	for(int i=1; i<=n; i++){
		set <pair <int, int> > :: iterator it = s.lower_bound({a[i]-mid+1, 0});
		l1 = (*it).ss-1;
		it = s.lower_bound({a[i]-2*mid+1, 0});
		l2 = (*it).ss-1;
		for (int x=0; x<=n; x++) { 
			dp[i][x]=1e9;
			

			if(x==0){
				dp[i][x]=dp[l2][x]+1;
			}
			else{
				dp[i][x]=min(dp[l1][x-1], dp[l2][x]+1);
			}		
			if (i==n && x<=p && dp[i][x]<=q) return 1;
		}
	}
	return 0;
}
signed main() {
	cin >> n >> p >> q;
	
	for(int i=1; i<=n; i++){
		cin >> a[i];
	}
	sort(a+1, a+n+1);
	for (int i=1; i<=n; i++) {
		s.insert({a[i], i});
	}
	int l=1, r=1e9;
	while(l<=r){
		int mid=(l+r)/2;
		if(check(mid)){
			ans=mid;
			r=mid-1;
		} else l=mid+1;
	}
	cout << ans;
}

Subtask #1

50.0 / 50.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	2392 KB	Output is correct
2	Correct	0 ms	344 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	1 ms	2392 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	2392 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	2396 KB	Output is correct
12	Correct	1 ms	2396 KB	Output is correct
13	Correct	1 ms	2396 KB	Output is correct
14	Correct	1 ms	2396 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	170 ms	31836 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	143 ms	31836 KB	Output is correct
4	Correct	143 ms	32212 KB	Output is correct
5	Correct	138 ms	31836 KB	Output is correct
6	Correct	145 ms	31948 KB	Output is correct
7	Correct	141 ms	31968 KB	Output is correct
8	Correct	145 ms	31956 KB	Output is correct
9	Correct	144 ms	31948 KB	Output is correct
10	Correct	143 ms	31952 KB	Output is correct
11	Correct	158 ms	32084 KB	Output is correct
12	Correct	140 ms	31952 KB	Output is correct
13	Correct	145 ms	31952 KB	Output is correct
14	Correct	171 ms	32208 KB	Output is correct
15	Correct	155 ms	31964 KB	Output is correct