Submission #444350

#	Time	Username	Problem	Language	Result	Execution time	Memory
444350		fuad27	Watching (JOI13_watching)	C++14	0 / 100	16 ms	31692 KiB

watching

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n, p, q, a = 0 , b;
vector<int> A;
vector<vector<int>> dp(2001, vector<int> (2001, 0));
bool check(int w) {
	a = 0;
	int I = min(n, q);
	int J = min(n, q);
	for(int i = 0;i<=I;i++) {
		for(int j = 0;j<=J;j++) {
			if(i == 0 and j == 0) {
				dp[0][0] = 0;
				continue;
			}	
			if(i > 0) {
				a = dp[i-1][j];
				b = a;
				for(;A[b] + (2*w - 1)>=A[a] and a<n;a++);
			}
			dp[i][j] = a;
			if(j > 0) {
				a = dp[i][j-1];
				b = a;
				for(;A[b] + (2*w - 1)>=A[a] and a<n;a++);
			}
			dp[i][j] = max(a, dp[i][j]); 
			a = 0;
		}
	}
	return (dp[I][J]>=n);
}
int32_t main () {
	cin >> n >> p >> q;
	for(int i = 0;i<n;i++) {
		int ai;
		cin >> ai;
		A.push_back(ai);
	}
	sort(A.begin(), A.end());
	int r = 1e9, l = 0, ans = 0;
	while(l<=r) {
		int mid = (l+r)/2;
		if(check(mid)) {
			r = mid - 1;
		}
		else {
			l = mid + 1;
		}
	}
	cout<<l<<endl;
	return 0;
}

Compilation message (stderr)

watching.cpp: In function 'int32_t main()':
watching.cpp:42:22: warning: unused variable 'ans' [-Wunused-variable]
   42 |  int r = 1e9, l = 0, ans = 0;
      |                      ^~~

• Subtask 1: 0 / 50
• Subtask 2: 0 / 50