Submission #797858

#	Time	Username	Problem	Language	Result	Execution time	Memory
797858		OrazB	Watching (JOI13_watching)	C++14	50 / 100	1077 ms	8200 KiB

watching

#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 (stderr)

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 / 50
• Subtask 2: 0 / 50