oj.uz

Submission #917320

# Submission time Handle Problem Language Result Execution time Memory
917320 2024-01-27T19:35:52 Z NintsiChkhaidze Watching (JOI13_watching) C++17
100 / 100
 231 ms 16212 KB 
#include <bits/stdc++.h>
#define ll long long
#define s second
#define f first
#define pb push_back
using namespace std;

const int N = 2e3 + 3,inf = 1e9;
int a[N],dp[N][N],n,p,q,arr[N];

int find(int i){
	int l = 1,r = n,res = 0;
	while (l <= r){
		int mid = (l + r)/2;
		if (a[mid] < i){
			res = mid;
			l = mid + 1;
		}else{
			r = mid - 1;
		}
	}
	return res;
}

bool check(int w){
	for (int i = 0; i <= n; i++)
		for (int j = 0; j <= p; j++)
			dp[i][j] = inf;
			
	dp[0][0] = 0;
	for (int i = 1; i <= n; i++){
		int l1 = find(a[i] - w + 1);
		int l2 = find(a[i] - 2*w + 1);
		for (int j = 0; j <= p; j++){
			//davsvat patara
			dp[i][j + 1] = min(dp[i][j + 1],dp[l1][j]);

			//davsvat didi
			dp[i][j] = min(dp[i][j],dp[l2][j] + 1);
		}
	}

	for (int i = 0; i <= p; i++)
		if (dp[n][i] <= q) return 1;
	return 0;
}
signed main() {
	ios_base::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL);
	 
	cin >> n >> p >> q;
	for (int i = 1; i <= n; i++)
		cin >> arr[i];
	sort(arr+1,arr+n+1);

	int m = 0;
	for (int i = 1; i <= n; i++){
		if (i == n || arr[i] != arr[i + 1]) {
			a[++m] = arr[i];
		}
	}
	n = m;

	p = min(p,n);
	q = min(q,n);

	int l = 0,r = 1e9,res=-1;
	while (l <= r){
		int w = (l + r) >> 1;
		if (check(w)) {
			res = w;
			r = w - 1;
		}else{
			l = w + 1;
		}
	}
	cout<<res;
}

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 344 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 2392 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 2604 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 5 ms 15452 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 229 ms 15964 KB Output is correct
4 Correct 216 ms 16212 KB Output is correct
5 Correct 16 ms 15452 KB Output is correct
6 Correct 214 ms 15960 KB Output is correct
7 Correct 7 ms 15448 KB Output is correct
8 Correct 19 ms 15452 KB Output is correct
9 Correct 84 ms 15708 KB Output is correct
10 Correct 231 ms 16108 KB Output is correct
11 Correct 18 ms 15448 KB Output is correct
12 Correct 126 ms 15964 KB Output is correct
13 Correct 8 ms 15452 KB Output is correct
14 Correct 11 ms 15340 KB Output is correct
15 Correct 10 ms 15448 KB Output is correct