oj.uz

Submission #797855

# Submission time Handle Problem Language Result Execution time Memory
797855 2023-07-30T03:14:55 Z OrazB Watching (JOI13_watching) C++14
50 / 100
 1000 ms 15348 KB 
#include <bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(), (x).end()
#define ll long long int
#define pii pair <int, int>
#define pb push_back
#define ff first
#define ss second

const int N = 1e5+5;
int a[N];

int main ()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n, p, q;
	cin >> n >> p >> q;
	for (int i = 1; i <= n; i++) cin >> a[i];
	sort(a+1,a+n+1);
	if (p+q >= n) return cout << 1, 0;
	int l = 1, r = 1e9, ans = -1;
	while(l <= r){
		int md = (l+r)>>1;
		vector<vector<int>> dp(n+1, vector<int>(p+1, 1e9));
		for (int i = 0; i <= p; i++) dp[0][i] = 0;
		for (int i = 1; i <= n; i++){
			for (int j = 0; j <= p; j++){
				int x = 1, y = i, pos;
				while(x <= y){
					int mid = (x+y)>>1;
					if (a[mid] > a[i]-md){
						pos = mid;
						y = mid - 1;
					}else x = mid + 1;
				}
				if (j) dp[i][j] = min(dp[i][j], dp[pos-1][j-1]);
				x = 1, y = i;
				while(x <= y){
					int mid = (x+y)>>1;
					if (a[mid] > a[i]-2*md){
						pos = mid;
						y = mid - 1;
					}else x = mid + 1;
				}
				dp[i][j] = min(dp[i][j], dp[pos-1][j]+1);
			}
		}
		if (*min_element(all(dp[n])) <= q){
			ans = md;
			r = md - 1;
		}else l = md + 1;
	}
	cout << ans;
}

Compilation message

watching.cpp: In function 'int main()':
watching.cpp:37:43: warning: 'pos' may be used uninitialized in this function [-Wmaybe-uninitialized]
   37 |     if (j) dp[i][j] = min(dp[i][j], dp[pos-1][j-1]);
      |                                        ~~~^~

Subtask #1
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 324 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 324 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 328 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 2 ms 340 KB Output is correct
12 Correct 2 ms 340 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 340 KB Output is correct

Subtask #2
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 340 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 28 ms 560 KB Output is correct
8 Correct 143 ms 1404 KB Output is correct
9 Correct 855 ms 6364 KB Output is correct
10 Execution timed out 1076 ms 15348 KB Time limit exceeded
11 Halted 0 ms 0 KB -