oj.uz

Submission #797856

# Submission time Handle Problem Language Result Execution time Memory
797856 2023-07-30T03:21:19 Z OrazB Watching (JOI13_watching) C++14
0 / 100
 145 ms 2644 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 <= p; 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
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 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 1 ms 212 KB Output is correct
9 Runtime error 1 ms 468 KB Execution killed with signal 6
10 Halted 0 ms 0 KB -

Subtask #2
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 440 KB Output is correct
2 Correct 0 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 212 KB Output is correct
7 Correct 30 ms 468 KB Output is correct
8 Correct 145 ms 1372 KB Output is correct
9 Runtime error 6 ms 2644 KB Execution killed with signal 6
10 Halted 0 ms 0 KB -