oj.uz

Submission #947118

# Submission time Handle Problem Language Result Execution time Memory
947118 2024-03-15T14:07:33 Z sandrofeiqrishvili Watching (JOI13_watching) C++14
50 / 100
 1000 ms 31716 KB 
#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++){
		for (int x=0; x<=n; x++) { 
			dp[i][x]=1e9;
			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;

			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 7 ms 2392 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 5 ms 2396 KB Output is correct
5 Correct 5 ms 2396 KB Output is correct
6 Correct 5 ms 2396 KB Output is correct
7 Correct 5 ms 2560 KB Output is correct
8 Correct 5 ms 2396 KB Output is correct
9 Correct 5 ms 2396 KB Output is correct
10 Correct 5 ms 2396 KB Output is correct
11 Correct 5 ms 2396 KB Output is correct
12 Correct 6 ms 2396 KB Output is correct
13 Correct 5 ms 2396 KB Output is correct
14 Correct 5 ms 2396 KB Output is correct
15 Correct 5 ms 2396 KB Output is correct

Subtask #2
0 / 50.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1055 ms 31716 KB Time limit exceeded
2 Halted 0 ms 0 KB -