Submission #797855

#	Time	Username	Problem	Language	Result	Execution time	Memory
797855		OrazB	Watching (JOI13_watching)	C++14	50 / 100	1076 ms	15348 KiB

watching

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

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