oj.uz

Submission #797858

# Submission time Handle Problem Language Result Execution time Memory
797858 2023-07-30T03:22:32 Z OrazB Watching (JOI13_watching) C++14
50 / 100
 1000 ms 8200 KB 
#include <bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(), (x).end()

const int N = 2e3+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>(min(p+1,q+1), 1e9));
		for (int i = 0; i <= min(p,q); i++) dp[0][i] = 0;
		for (int i = 1; i <= n; i++){
			for (int j = 0; j <= min(p,q); j++){
				int x = 1, y = i, pos1; 
				while(x <= y){
					int mid = (x+y)>>1;
					if (a[mid] > a[i]-md){
						pos1 = mid;
						y = mid - 1;
					}else x = mid + 1;
				}
				x = 1, y = i;
				int pos2;
				while(x <= y){
					int mid = (x+y)>>1;
					if (a[mid] > a[i]-2*md){
						pos2 = mid;
						y = mid - 1;
					}else x = mid + 1;
				}
				if (p <= q){
					if (j) dp[i][j] = min(dp[i][j], dp[pos1-1][j-1]);
					dp[i][j] = min(dp[i][j], dp[pos2-1][j]+1);
				}else{
					if (j) dp[i][j] = min(dp[i][j], dp[pos2-1][j-1]);
					dp[i][j] = min(dp[i][j], dp[pos1-1][j]+1);
				}
			}
		}
		if (*min_element(all(dp[n])) <= max(p,q)){
			ans = md;
			r = md - 1;
		}else l = md + 1;
	}
	cout << ans;
}

Compilation message

watching.cpp: In function 'int main()':
watching.cpp:43:38: warning: 'pos2' may be used uninitialized in this function [-Wmaybe-uninitialized]
   43 |      dp[i][j] = min(dp[i][j], dp[pos2-1][j]+1);
      |                                  ~~~~^~
watching.cpp:42:45: warning: 'pos1' may be used uninitialized in this function [-Wmaybe-uninitialized]
   42 |      if (j) dp[i][j] = min(dp[i][j], dp[pos1-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 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 2 ms 212 KB Output is correct
11 Correct 2 ms 212 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 212 KB Output is correct

Subtask #2
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 340 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 280 KB Output is correct
7 Correct 29 ms 528 KB Output is correct
8 Correct 193 ms 1388 KB Output is correct
9 Correct 185 ms 1408 KB Output is correct
10 Correct 115 ms 1092 KB Output is correct
11 Correct 118 ms 1260 KB Output is correct
12 Execution timed out 1077 ms 8200 KB Time limit exceeded
13 Halted 0 ms 0 KB -